CS Paper Radar

Characterizations and MacWilliams-Like Identities of Weakly Regular Bent Partitions

Jiaxin Wang, Yadi Wei, Fang-Wei Fu, Jin Li, Fulin Li

cs.IT ·submitted 2026-10-30 14:16 UTC · v1
theory

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}$.

Closest papers

Nearest neighbours by meaning across the whole index.

General constructions of normal bent partitions related to vectorial dual-bent functions

cs.DM math.CO ·2026-10-02 ·Alexander Kholosha, Mohit Pal
theory similarity 0.71
Abstract

Bent partitions were introduced as a generalization of partial spread construction of bent functions and they became a hot research topic recently. In this paper, we prove two general constructions of normal bent partitions that are related to vectorial dual-bent functions. They cover many of the currently known bent partitions of this type as partial cases. These constructions also provide a large number of new bent partitions. Relevant properties of bent functions obtained from such partitions are proven.

0.23

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

cs.IT cs.DM ·2026-09-16 ·Alexander Kholosha, Mohit Pal
similarity 0.63
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

Fine Difference Structure and Prime-Power Depth of Bent Partitions

cs.IT math.CO ·2026-08-28 ·Zhaorui Wu
theory similarity 0.59
Abstract · 8 pages. Ancillary files contain the Lean 4 formalization, axiom audits, and reproducibility materials

A $p$-ary bent partition of $\mathbb{F}_p^n$ is a partition into $K$ nonempty cells such that every balanced assignment of its cells to $\mathbb{F}_p$ produces a bent function. It was asked whether every possible depth $K$ is a power of $p$; for general $p$, previous affirmative results required regularity or cell-symmetry hypotheses. We prove the stronger unconditional statement that, for every nonzero $h$, exactly $p^n/K$ points remain in the same fine cell under translation by $h$. Thus the fine cells form a partitioned difference family and the fine label map is zero-difference balanced. Consequently $K\mid p^n$, so $K=p^t$; nonempty cells further give $1\le t<n$. In even dimension, the classical cell-size theorem yields $K\mid p^{n/2}$. Together with the known odd-dimensional ternary three-fibre parameter restriction, this gives the global bound $t\le\lfloor n/2\rfloor$. The proof is an exact finite average over balanced coarsenings. The main counting identity and selected consequences are formalized and kernel-checked in Lean 4.

0.28

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

cs.IT math.CO ·2026-09-12 ·Yansheng Wu, Jiaxin Wang, Jong Yoon Hyun
similarity 0.57
Abstract · 16 pages

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.

0.26

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.56
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

A Hyperplane Bound and Ward's Divisibility Conjecture

cs.IT ·2026-10-19 ·Guanghui Zhang
theoryhot direction similarity 0.50
Abstract · 31 pages

Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,ν_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bound independent of dimension: a nonzero scalar-invariant function $F:\mathbb{F}_q^k\to\mathbb{F}_p$, with $F(0)=0$ and prime-field algebraic degree at most $(f+s)(p-1)$, vanishes identically on at most $p^s(q-1)$ linear hyperplanes when $0\le s<f$. A truncated digit-sum inequality forces selected coefficient polynomials to be homogeneous of ordinary degree less than $q$. Weighted moments on a projective line then bound their linear factors, while a second-moment argument handles the complementary support configuration. An elementary finite-difference calculation supplies the degree bound for divided weight residues. Endpoint shortenings prove the basic divisibility layers; endpoint lifting, a surjective linear functional, and residual-code induction extend the argument to every valuation. We include the proofs of the classical ingredients, identify their sources, and distinguish the present argument from an earlier reported unpublished proof.

0.53

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

cs.IT ·2026-09-18 ·Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou
hot direction similarity 0.50
Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

0.34

Helly-Type Theorems for Splitting Point Sets

cs.CG math.COcs.DM ·2026-09-02 ·Lidor Portal, Natan Rubin
top venue similarity 0.49
Abstract · A preliminary version appeared in the Proceeding of SODA 2026

Let $0 < α\leq 1/2$. We say that a finite point set $P$ in $\mathbb{R}^d$ is $α$-split by a hyperplane $h$ if each of the closed half-spaces determined by $h$, contains at least $α|P|$ of the points of $P$. We further say $P$ is $α$-split by a $k$-dimensional flat $τ$ if $P$ is $α$-split by any hyperplane through $τ$. In the standard notation (which coincides with Tukey depth for $k= 0$), the $k$-flat $τ$ has depth $α$ with respect to $P$. We establish interesting Helly-type theorems for splitting families of finite point sets in $\mathbb{R}^d$. Unlike the classical sufficient Helly-type criteria for transversals to families of compact convex sets, which exist only for point and hyperplanes, our results extend to splitting families of point sets by collections of $k$-flats of arbitrary dimensionality $ 0 \leq k \leq d-1$.

0.40