CS Paper Radar

A Novel Approach to Counterexamples of the Polujan-Pott Conjecture via Set-Partition Permutations

Yansheng Wu, Jiaxin Wang, Jong Yoon Hyun

cs.IT math.CO ·submitted 2026-09-12 14:35 UTC · v1

Abstract

In this paper, we settle a conjecture of Polujan and Pott by constructing an explicit, infinite family of Maiorana--McFarland bent functions $f_t$ in $2(2^t-1)$ variables with algebraic degree $°(f_t) = t + 1$ for any integer $t \ge 2$. Our construction builds upon a minimal commutative algebra $I_t$, which naturally induces a triangular set-partition polynomial permutation $P_t$. By identifying an elementary abelian subgroup within the direct sum $ I_t \oplus I_t^*$, we establish an explicit nonlinear coordinate transformation that pulls $f_t$ back to a canonical quadratic form. This linearizes the translation development $\operatorname{Dev}(D_{f_t})$ under an exotic group structure and proves that it is isomorphic to the classical symplectic design $S^\pm(2(2^t-1))$, thereby fully resolving the conjecture.

Comment
16 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Reduced APN permutations and a disproof of the Galois-ring lifting conjecture

cs.IT math.NT ·2026-08-31 ·Daniele Bartoli, Pantelimon Stanica
similarity 0.58
Abstract

We construct infinite families of reduced almost perfect nonlinear (APN) permutations of $\mathbb{F}_{2^m}$ that admit coefficientwise permutation lifts to $\mathrm{GR}(2^k,m)$ for every $k>1$. These families disprove Conjecture~2 of Rønjom and Sandrib (Cryptogr. Commun., 2026), even for reduced polynomial representatives. For every odd $m\ge5$ with $3\nmid m$, we obtain explicit seven-term polynomials over $\mathbb{F}_2$ with formal derivative identically one. We derive them from a complete criterion for the reduced representative of $A(x)^{2^s+1}$ to have no critical point in $\mathbb{F}_{2^m}$, where $A$ is an invertible linearized polynomial and $\gcd(s,m)=1$. We then apply the cube case to construct a second family of degree $2^{m-1}+2$, whose nonconstant derivatives avoid zero by an explicit trace identity. A fixed parameter in $\mathbb{F}_{32}$ gives this family in every dimension $m=5r$ with $r$ odd, including a degree-$18$ example over $\mathbb{F}_{32}$. Both constructions remain in Gold linear equivalence classes, so liftability of reduced representatives is not invariant under invertible $\mathbb{F}_2$-linear input changes. We obtain the lifting conclusions from the standard Galois-ring permutation criterion. We also verify a degree-$24$ example supplied by Zhang and Haobo, prove a trace-adjoint criterion for reduced quadratic functions, and interpret the derivative condition through ramification at rational points.

0.44

Characterizations and MacWilliams-Like Identities of Weakly Regular Bent Partitions

cs.IT ·2026-10-30 ·Jiaxin Wang, Yadi Wei, Fang-Wei Fu, Jin Li, Fulin Li
theory similarity 0.57
Abstract

Bent partitions play a significant role in the theory of bent functions. In this paper, we study weakly regular bent partitions, that is, all generated bent functions are weakly regular (called in class $\mathcal{WRBP}$). Let $Γ=\{A_{i}, i \in V_{m}\}$ be a bent partition of $V_{n}$ in class $\mathcal{WRBP}$, where $V_{n}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$, $n$ is even, $m \leq \frac{n}{2}$, and $m \geq 2$ if $p=2$. We first characterize bent partition $Γ$ in terms of the duals of component functions of vectorial bent functions. In particular, we prove that if $p \neq 3$, then all bent functions generated by $Γ$ are regular. Building on the above result, we give characterizations of bent partition $Γ$ in terms of two classes of linear codes. When $n \geq 4$ and $m=\frac{n}{2}$, except for the case where $(p, n)=(2, 4)$ and $|A_{i_{0}}|=1$ for some $i_{0}$, we show that $Γ$ is obtained from a spread (after a shift). Particularly, any normal bent partition of $V_{n}$ of depth $p^{\frac{n}{2}}$ in class $\mathcal{WRBP}$ must be obtained from a spread (after a shift), where $n \geq 4$. We establish the Macwilliams-like identities for bent partitions in class $\mathcal{WRBP}$. Furthermore, if $p$ is odd, we present some nonexistence results on bent partitions in class $\mathcal{WRBP}$.

0.13

Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure

cs.IT ·2026-09-25 ·Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
theory similarity 0.56
Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ constructed from a recursively defined sequence of mappings $\{γ_j\}_{j\ge 0}$ associated with landscapes. First, we prove that, under an explicit dimension condition relating $n$ to the support of the landscape, the sequence $\{γ_j\}_{j\ge 0}$ has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on $\mathbb F_2^n$ with a nonzero special index. Then, we determine the eventual zero or periodic behavior of $\{γ_j\}_{j\ge0}$, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

0.07

Structure and Complexity of 2-Nilpotent Mal'cev Algebras

cs.CC math.RA ·2026-08-19 ·Patrick Wynne
similarity 0.53
Abstract

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

0.26

Generalized $p$-ary $\cPS$ Bent Functions

cs.IT cs.DM ·2026-09-16 ·Alexander Kholosha, Mohit Pal
similarity 0.52
Abstract

We use $m$-dimensional partial spreads of $\fp^{2n}$, where $p$ is an odd prime, $n$ is a positive integer and $m$ divides $n$, to construct two classes of bent functions from $\fp^{2n}$ to $\fp$. Our construction generalizes the classes of $p$-ary $\cPS^{-}$ and $\cPS^{+}$ bent functions proposed by P. Lison\v ek and H. Y. Lu (Des. Codes Cryptogr. 73 (2014), 209--216).

0.28

Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree

cs.DM math.CO ·2026-09-08 ·Songtao Mao
similarity 0.51
Abstract · 20 pages

We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-λ,λ]$ for every fixed $λ>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $Θ_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.

0.36

CCZ-Equivalence and Enumeration of Triprojective APN Functions

cs.CR ·2026-08-12 ·Jingchuan Ma, Yanhua Liu, Qiaoyun Huang
similarity 0.50
Abstract · 17 pages

We classify all admissible parameters of the G"ologlu--K"olsch triprojective construction of almost perfect nonlinear (APN) functions up to Carlet--Charpin--Zinoviev (CCZ) equivalence. The construction has three coefficients in $K=\mathbb{F}_{2^m}$ and a Frobenius exponent $k$ coprime to $m$. For every $m>1$, we give a necessary-and-sufficient criterion that includes changes of both the coefficients and the exponent. Each parameter choice determines one of the two irreducible cubic polynomials over $\mathbb{F}_2$. Two functions are equivalent precisely when their exponents and cubics agree, or when the exponents are negatives modulo $m$ and the cubics are reciprocal. When $7\nmid m$, every admissible member is equivalent to a Li--Kaleyski representative: the larger coefficient space adds no CCZ classes. When $7\mid m$, those representatives are inadmissible; we construct replacements and classify the full family. There are exactly $\varphi(m)$ CCZ classes, extending the previously known count for the older subfamilies to all admissible coefficients and all degrees. We also count the parameter triples and compute canonical representatives and explicit equivalence maps in deterministic polynomial time for every degree, including degrees divisible by seven. The proof combines a reduction to classical semilinear conjugacy with an intrinsic recovery of the scalar field from the polar bilinear map. The reduction from arbitrary EL equivalence is algebraic in every degree, including degrees three and six.

0.10

A counterexample to Tokareva's conjecture on sums of two bent functions

cs.IT math.CO ·2026-10-23 ·Yansong Feng, Hao Jiang, Guancheng Li, Tianyi Li, Lili Tang
similarity 0.50
Abstract · The counterexamples and proofs in this paper were obtained through large-scale automated reasoning with LLM agents while solving Problem~10 …

It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ and for several special classes of Boolean functions. We disprove this conjecture by showing that $x_1x_2(x_3x_4+x_5x_6+x_7x_8)$ is not a sum of two bent functions on $\mathbb{F}^8$. We extend this construction to obtain counterexamples in every even dimension $n\ge 8$. Using Shaporenko's reduction, we also obtain explicit counterexamples to Tokareva's derivative conjecture in every even dimension $n\ge 10$.

0.47