Source-linked AI summary
Fine Difference Structure and Prime-Power Depth of Bent Partitions
Zhaorui Wu
TL;DR
The paper addresses whether p-ary bent partitions necessarily have prime-power depth, a question previously settled only under extra regularity or symmetry assumptions. Using an exact finite average over balanced coarsenings, it proves an unconditional same-cell translation count, yielding K = p^t and the bound t ≤ floor(n/2).
Problem
The paper asks whether every p-ary bent partition must have prime-power depth, beyond earlier results requiring regularity or cell-symmetry hypotheses.
Method
The proof averages coarse derivative counts over balanced coarsenings to recover the exact fine same-cell diagonal for each nonzero translation.
Results
K D_h = p^n for every nonzero h, so every bent partition is a PDF and its label map is ZDB; consequently K = p^t, with t ≤ floor(n/2).
Takeaways & Limitations
The formerly conditional prime-power-depth conclusion holds unconditionally, and the fine cells necessarily carry partitioned-difference-family structure.
Takeaways & Limitations
No converse is established: prime-power depth is only necessary, and fine ZDB counts alone do not recover the universal bent-coarsening axiom.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper resolves whether every p-ary bent partition must have prime-power depth by recovering exact same-cell translation counts from universal balanced coarsenings. This yields unconditional divisibility and a global bound on the exponent.
- Problem: The bent-partition hypothesis requires every balanced assignment of the K fine cells to F_p to produce a bent function.The universality concerns every balanced coarsening of one fixed fine partition.
- Main counting identity: K D_h = p^n for every nonzero translation h, where D_h is the same-cell count recovered by averaging balanced coarsenings.Distinct fine labels collide with probability (m − 1)/(K − 1) when K = p^m, while every coarse derivative has p^(n−1) zeros.
- Structural consequence: The fine cells form a partitioned difference family, equivalently the fine label map is zero-difference balanced, before any prime-power structure on the label set is assumed.The PDF and ZDB formulations use the same zero-difference count.
- Depth: K divides p^n, so K = p^t without regularity, weak regularity, or cell-symmetry assumptions; nonempty cells give 1 ≤ t < n.This is the paper’s unconditional prime-power-depth conclusion.
- Dimension bound: t ≤ floor(n/2), combining the new divisibility with the established even-dimensional and odd-dimensional ternary parameter restrictions.The odd-dimensional case is handled under its correct ternary hypothesis rather than by applying the even-dimensional formula.
2. Definitions
The paper defines bent partitions through universal balanced coarsenings and derives the uniform derivative-fibre law for p-ary bent functions. It then relates same-cell translation counts to PDF and ZDB terminology.
- Derivative balance: p^(n−1) points satisfy Δ_h f(x) = a for every nonzero h and every a ∈ F_p when f is p-ary bent.This is the standard derivative consequence of p-ary bentness.
- Proof mechanism: The derivative-fibre law follows from Walsh flatness and finite Fourier inversion, using the minimal polynomial of the primitive p-th root of unity.The polynomial argument forces all derivative-value counts N_a to be equal, and their sum is p^n.
- Bent partitions: A fibre partition of a surjective label map L: V → I is bent of depth K when every balanced c: I → F_p makes c ◦ L bent.Here I has K elements and K = p^m.
- PDF and ZDB: A partitioned difference family consists of disjoint blocks partitioning a finite additive group with a prescribed nonzero-difference multiplicity.The corresponding ZDB condition counts x with L(x + h) = L(x) for each nonzero h.
- PDF and ZDB: PDF and ZDB are equivalent descriptions of the same equality-only same-label translation condition, independent of any group structure chosen on I.After identifying I with a group of order K, the label map satisfies the usual ZDB condition.
3. A balanced-fusion lemma
The balanced-fusion lemma recovers the hidden same-label diagonal by averaging collision counts over balanced maps. Its combinatorial proof requires neither a group structure nor a Walsh transform.
- Setup: The lemma considers finite sets X and I, a map L: X → I, a self-map T of X, and balanced maps c: I → [b].It defines Z_c(T) as the number of coarse-label collisions and D_T as the number of fine-label collisions.
- Collision counting: Equal fine labels always collide under c, while distinct labels collide with a uniform probability determined by balanced-map counting.Conditioning on one label gives the pairwise collision probability used in the average.
- Recovery: Pointwise averaging of Z_c(T) separates the fine-label diagonal D_T from the off-diagonal collisions.This is the recovery mechanism behind the lemma.
- Generality: The argument is an exact finite average and extends to any distribution on balanced maps with equal collision probability for every distinct label pair.No group or Walsh-transform structure is needed for this combinatorial step.
4. The fine PDF and prime-power depth
The fine-label collision identity shows that every nonzero translation preserves exactly p^n/K same-cell points, yielding PDF and ZDB structure. Its arithmetic consequences force prime-power depth, strict bounds, and the dimension-sensitive restriction t ≤⌊n/2⌋.
- Fine PDF/ZDB theorem: For every nonzero h, exactly p^n/K points satisfy L(x+h)=L(x).This identity is obtained by averaging over balanced coarsenings and applying the bent-function collision count.
- Fine PDF/ZDB theorem: The fine cells form a partitioned difference family of index p^n/K, and L is zero-difference balanced with the same parameter.
- Prime-power depth: Every p-ary bent partition has prime-power depth K=p^t with 1≤t≤n.The collision identity gives K∣p^n; primality of p then yields the prime-power form.
- Contribution: The result resolves prime-power depth unconditionally, without regularity or cell-symmetry hypotheses, and strengthens divisibility to the PDF/ZDB property.
- Prime-power depth: Nonempty cells strengthen the bound to 1≤t<n, equivalently K<p^n.Surjectivity and the positive same-label count exclude injectivity.
- Dimension-sensitive refinement: The global dimension-sensitive bound is 1≤t≤⌊n/2⌋: even n gives K∣p^(n/2), while odd n permits only (p,K)=(3,3).The even case uses the classical cell-size theorem; the odd case uses the cited ternary parameter restriction and excludes n=1.
5. Consequences and limits
The fine PDF/ZDB structure fixes cell-size moments and supports stronger vectorial derivative laws, while transition measurements have documented non-injectivity and the converse remains unavailable.
- Cell-size consequences: The fine PDF identity fixes the second moment of the cell sizes.It follows by counting ordered same-cell pairs by their translation difference.
- Vectorial consequence: Once the depth is prime-power, relabelling the partition yields a surjective vectorial bent map whose nonzero derivatives are uniformly distributed.For every nonzero h and every output difference u, the derivative fibre has size p^(n−t).
- Finite obstruction: Five balanced coarsenings rule out depth six within the stated pair-uniform scheme.The five equal-colour pairings form a one-factorization of K6; four coarsenings outside that scheme are not excluded.
- Limits: No converse is established: fine ZDB counts alone do not recover the universal bent-coarsening axiom, and prime-power depth is only necessary for existence.Normal bent partitions also fall outside direct application of the main theorem because of their distinguished cell and two-level law.
- Limits: The transition-measurement operator is non-injective on the ambient zero-margin perturbation space, although this does not assert identical data for realizable bent partitions.The trace statistic recovered by the universal axiom remains unaffected.
6. Lean formalization
The main counting identity and selected arithmetic and obstruction results were formalized and kernel-checked in Lean 4.32.0 with mathlib 4.32.0.
- Scope: Lean 4.32.0 with mathlib 4.32.0 kernel-checked the balanced-fusion lemma, the fine PDF/ZDB count, arithmetic consequences, the cell-size moment, and transition obstruction.The formalization accepts the classical even-dimensional cell-size divisibility theorem as an explicit input and does not reprove it or the odd-dimensional classification.
7. Conclusion
The universal balanced-coarsening axiom determines exact same-cell translation counts, yielding PDF/ZDB structure and unconditional prime-power depth divisibility. The conclusion also records limits on converse inference and transition measurements.
- Main conclusion: For every nonzero translation, the universal axiom determines the hidden same-cell diagonal exactly.Every bent partition is therefore a PDF, its label map is ZDB, and its depth divides p^n.
- Main conclusion: The formerly conditional prime-power conclusion follows using only derivative balance and an exact finite collision average.The result removes regularity and symmetry assumptions.
- Limits: The associated measurement operator is non-injective on the ambient real zero-margin perturbation space, without implying two realizable bent partitions share identical transition data.The trace remains the statistic recovered by the universal axiom.