Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
Pith reviewed 2026-05-25 07:04 UTC · model grok-4.3
The pith
Asymptotically almost all vectorial functions over finite fields have trivial extended-affine stabilizers.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that the set of vectorial functions over a finite field whose extended-affine stabilizer is larger than the identity has asymptotic density zero. Consequently the number of EA-equivalence classes equals the naive count (total functions divided by group order) multiplied by (1 + o(1)). Upper bounds on the size of EA- and CCZ-orbits follow, and the probability that two independently chosen functions lie in the same EA-orbit is shown to be super-exponentially small.
What carries the argument
The extended-affine stabilizer of a vectorial function, i.e., the subgroup of extended-affine transformations that leave the function invariant.
If this is right
- The number of EA-equivalence classes equals the total number of functions divided by the EA-group order, up to a factor 1 + o(1).
- Two independently sampled vectorial functions are EA-equivalent with super-exponentially small probability.
- The subset of functions possessing nontrivial EA-stabilizers is exponentially rare.
- Upper bounds hold for the probability of CCZ-equivalence between random functions.
Where Pith is reading between the lines
- Random sampling becomes a reliable method for generating functions without accidental symmetries.
- Classification or enumeration algorithms for large fields can safely ignore the rare symmetric cases.
- Similar density statements may hold for other group actions on functions over finite fields.
Load-bearing premise
The counting and probability estimates are performed in the regime where the dimension of the underlying vector space tends to infinity.
What would settle it
A construction or counting argument that produces a positive-density subset of vectorial functions with nontrivial EA-stabilizers for arbitrarily large field dimensions would falsify the claim.
read the original abstract
We prove that asymptotically almost all vectorial functions over finite fields have trivial extended-affine stabilizers. As a consequence, the number of EA-equivalence classes is asymptotically equal to the naive estimate, namely the total number of functions divided by the size of the EA-group, with vanishing relative error. Furthermore, we derive upper bounds on collision probabilities for both extended-affine and CCZ equivalences. For EA-equivalence, we leverage the trivial-stabilizer result to establish a matching lower bound, yielding a tight asymptotic formula that shows two independently sampled functions are EA-equivalent with super-exponentially small probability. The results validate random sampling strategies for cryptographic primitive design and show that functions with nontrivial EA-stabilizers form an exponentially rare subset.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that asymptotically almost all vectorial functions over finite fields have trivial extended-affine stabilizers. The central argument is a union bound showing that the proportion of functions fixed by any non-identity element of the EA group tends to zero as dimension n tends to infinity, since for each fixed g ≠ 1 the probability a random function is fixed by g is at most q^{-c n} while the group order is only exp(O(n^2)). Consequences include that the number of EA-equivalence classes equals the total number of functions divided by |EA| with vanishing relative error, plus tight asymptotic collision probabilities for EA-equivalence (super-exponentially small) and upper bounds for CCZ-equivalence.
Significance. If the counting bounds hold, the result rigorously justifies random sampling for cryptographic primitive design, as the subset with nontrivial EA-stabilizers is exponentially rare. Credit is due for the clean application of the standard union-bound technique for generic freeness of a group action on a large finite set, which directly yields the matching lower bound on collision probability and the asymptotic formula for the number of classes.
Simulated Author's Rebuttal
We thank the referee for the positive report and the recommendation to accept. The assessment accurately captures the main contribution: the union-bound argument establishing that the proportion of functions with nontrivial EA-stabilizers vanishes, together with the resulting asymptotic count of EA-classes and the collision-probability bounds.
Circularity Check
No circularity; direct counting argument via union bound
full rationale
The paper establishes the main result by a standard union-bound argument: for each fixed non-identity g in the EA group, the probability that a random function is fixed by g is at most q^{-c n} for c>0, while |EA| is only exponential in O(n^2), so the proportion of functions with nontrivial stabilizer vanishes as n→∞. This is a self-contained probabilistic counting proof with no fitted parameters, no self-definitional steps, and no load-bearing self-citations. The consequence about the number of EA-classes equaling the naive estimate follows directly from the trivial-stabilizer result without circular reduction. No step reduces to its own input by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard algebraic properties of finite fields and the definition of the extended-affine group action on the set of vectorial functions
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.