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
Method
Results
Takeaways & Limitations
The formerly conditional prime-power-depth conclusion holds unconditionally, and the fine cells necessarily carry partitioned-difference-family structure.
Source: §7 · p. 7No converse is established: prime-power depth is only necessary, and fine ZDB counts alone do not recover the universal bent-coarsening axiom.
Source: §5 · p. 6
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.Source: §1 · p. 1
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.Source: §1 · p. 2
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.Source: §1 · p. 2
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.Source: §1 · p. 2
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.Source: §1 · p. 2
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.Source: §2 · p. 2
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.Source: §2 · p. 3
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.Source: §2 · p. 3
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.Source: §2 · p. 3
- 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.Source: §2 · p. 3
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.Source: §3 · p. 3
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.Source: §3 · p. 4
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.Source: §3 · pp. 3–4
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.Source: §3 · pp. 3–4
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.Source: §4 · p. 4
- The fine cells form a partitioned difference family of index p^n/K, and L is zero-difference balanced with the same parameter.Source: §4 · p. 4
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.Source: §4 · p. 4
Contribution
- The result resolves prime-power depth unconditionally, without regularity or cell-symmetry hypotheses, and strengthens divisibility to the PDF/ZDB property.Source: §4 · p. 4
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.Source: §4 · p. 4
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.Source: §4 · p. 5
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.Source: §5 · p. 5
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).Source: §5 · pp. 5–6
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.Source: §5 · p. 6
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.Source: §5 · pp. 6–7
- 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.Source: §5 · pp. 6–7
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.Source: §6 · p. 7
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.Source: §7 · p. 7
- The formerly conditional prime-power conclusion follows using only derivative balance and an exact finite collision average.The result removes regularity and symmetry assumptions.Source: §7 · pp. 7–8
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.Source: §7 · p. 8