spread_line_contained_in_non_bent
Let E be a finite field equipped with an algebra structure over ZMod 2 such that the cardinality of E is 2^(2m), where m is an odd natural number. For any element a in nonzero_cubes E, the subspace spread_subspace E m a is contained in non_bent_components E m a ∪ {0}.
Statement
theorem spread_line_contained_in_non_bent {E : Type*} [Field E] [Fintype E] [Algebra (ZMod 2) E] (m : ℕ) (hm : Odd m) (hcard : Fintype.card E = 2 ^ (2 * m)) (a : E) (ha : a ∈ nonzero_cubes E) : (spread_subspace E m a : Set E) ⊆ non_bent_components E m a ∪ {0}
- Formalizes
- arXiv:2611.10269 Proposition 11
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- nonzero_cubesThe set of nonzero cubes in a field E, consisting of all elements of the form x^3 for nonzero x in E.
- non_bent_componentsFor a finite field $E$ of characteristic 2 (equipped with an algebra structure over $\mathbb{Z}/2\mathbb{Z}$), a natural number $m$, and…
- spread_subspaceFor an element a in a field E of characteristic 2, the spread line subspace a * F_q is the F_2-submodule generated by all products a * t…
- nonzero_cubes_mulIn any field, the product of two nonzero cubes is itself a nonzero cube.
- subfield_nonzero_mem_cubesLet E be a field, m an odd natural number, and t a nonzero element of E. If t^(2^m) = t, then t belongs to nonzero_cubes E.
- subfield_element_trace_zeroLet E be a finite field of characteristic 2 with 2^(2m) elements. Then the absolute trace of any element t in E satisfying t^(2^m) = t is…
- apn_family_fa_component_eq_cubicLet a and β be elements of a finite field E of characteristic 2 such that the absolute trace of β * a⁻¹ is 0. Then for all x in E, the…
- cubic_power_component_cube_non_bentLet E be a finite field of characteristic 2 with 2^(2m) elements. If β in E is a nonzero cube, then the Boolean function x ↦ Tr(β x^3) is…
- is_field_bentA Boolean function f : E → ZMod 2 on a finite field E of dimension 2m over F_2 is bent if its Walsh transform coefficient at every…
- apn_family_faFor an element a in a finite field E of characteristic 2, the function F_a(x) is defined by x^3 + a⁻¹ * Tr(a^3 * x^9).
Read back from the Lean
Let $E$ be a finite field that is an algebra over $\mathbb{Z}/2\mathbb{Z}$. Let $m$ be an odd natural number, and assume the cardinality of $E$ is $2^{2m}$. Let $a \in E$ be a non-zero cube in $E$ (i.e., $a = x^3$ for some $x \in E \setminus \{0\}$).
Then the $(\mathbb{Z}/2\mathbb{Z})$-submodule spread_subspace E m a is contained in non_bent_components E m a ∪ {0}.
In other words, every element $\beta$ in the $(\mathbb{Z}/2\mathbb{Z})$-linear span of $\{a \cdot t \mid t \in E, t^{2^m} = t\}$ is either $0$ or is a non-zero element such that the Boolean function
$$x \mapsto \mathrm{Tr}_{E/(\mathbb{Z}/2\mathbb{Z})}\left(\beta \left(x^3 + a^{-1} \cdot \mathrm{Tr}_{E/(\mathbb{Z}/2\mathbb{Z})}(a^3 x^9)\right)\right)$$
is not bent (that is, there exists $\alpha \in E$ whose Walsh transform $\sum_{x \in E} (-1)^{\mathrm{Tr}(\beta f_a(x)) + \mathrm{Tr}(\alpha x)}$ does not have absolute value $2^m$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that every element of the spread subspace is of the form a * t for some subfield element t ∈ F_{2^m} (where t^(2^m) = t), and that every such element belongs to non_bent_components E m a ∪ {0}. The representation β = a * t is established by induction on the submodule span, using the Frobenius endomorphism in characteristic 2 to show closure under addition. For any such element with t ≠ 0, both a and t are cubes (since m is odd), making a * t a nonzero cube; furthermore, the trace of (a * t) * a⁻¹ = t vanishes, which collapses the component function of f_a to a pure cubic power trace x ↦ Tr((a * t) * x^3), known not to be bent when the coefficient is a cube.
To show every element β in the spread subspace is of the form a * t with t^(2^m) = t, it suffices to prove this form for generators, zero, sums, and scalar multiples.
We establish that E has characteristic 2 from its algebra structure over ZMod 2 via charP_of_injective_algebraMap', and note 2^m ≠ 0 via pow_ne_zero. Unfolding the definition of spread_subspace, which is the submodule spanned over ZMod 2 by {a * t | t^(2^m) = t}, we apply Submodule.span_induction on the span.
uses
charP_of_injective_algebraMap',pow_ne_zero,Submodule.span_inductionhaveI : CharP E 2 := charP_of_injective_algebraMap' (ZMod 2) 2 have hpow : 2^m ≠ 0 := pow_ne_zero m (by norm_num) unfold spread_subspace at hβ refine Submodule.span_induction (p := fun x _ => ∃ t, t ^ (2^m) = t ∧ x = a * t) ?_ ?_ ?_ ?_ hβ
The representation β = a * t holds for generators and 0, and is closed under addition.
Generators have the required form by definition. For zero, 0 = a * 0 and 0^(2^m) = 0 by zero_pow and mul_zero. For a sum of two elements a * tx and a * ty, distributivity gives a * (tx + ty) via mul_add, and the Frobenius identity add_pow_char_pow in characteristic 2 shows (tx + ty)^(2^m) = tx^(2^m) + ty^(2^m) = tx + ty.
uses
zero_pow,mul_zero,add_pow_char_pow,mul_add· rintro x ⟨t, ht, rfl⟩ exact ⟨t, ht, rfl⟩ · exact ⟨0, by rw [zero_pow hpow], by rw [mul_zero]⟩ · rintro x y _ _ ⟨tx, htx, rfl⟩ ⟨ty, hty, rfl⟩ exact ⟨tx + ty, by rw [add_pow_char_pow, htx, hty], by rw [mul_add]⟩
The representation β = a * t is preserved under scalar multiplication by ZMod 2, completing the characterisation of elements in the spread subspace.
For any scalar c ∈ ZMod 2, a case check on c = 0 and c = 1 shows that (algebraMap (ZMod 2) E c)^(2^m) = algebraMap (ZMod 2) E c using map_pow, zero_pow, and one_pow. The scalar product c • (a * t) is then a * ((algebraMap (ZMod 2) E c) * t) by Algebra.smul_def, and the new parameter satisfies the subfield equation by mul_pow.
uses
map_pow,zero_pow,one_pow,mul_pow,Algebra.smul_def· rintro c x _ ⟨t, ht, rfl⟩ have hc : ((algebraMap (ZMod 2) E) c) ^ (2^m) = (algebraMap (ZMod 2) E) c := by rw [← map_pow] congr 1 fin_cases c · show (0 : ZMod 2) ^ (2^m) = 0 rw [zero_pow hpow] · show (1 : ZMod 2) ^ (2^m) = 1 rw [one_pow] refine ⟨(algebraMap (ZMod 2) E) c * t, ?_, ?_⟩ · rw [mul_pow, hc, ht] · rw [Algebra.smul_def]; ring
When t = 0, the element a * t is in the target set.
Splitting into cases with eq_or_ne, if t = 0 then a * 0 = 0, which trivially belongs to non_bent_components E m a ∪ {0}.
uses
eq_or_nercases eq_or_ne t 0 with rfl | ht · simp
When t ≠ 0, the product a * t is a nonzero cube in E.
Since a is a nonzero cube, a ≠ 0 by pow_ne_zero, so a * t ≠ 0 by mul_ne_zero. Because m is odd and t ≠ 0 satisfies t^(2^m) = t, subfield_nonzero_mem_cubes shows t is a cube in E. Since both a and t are nonzero cubes, their product a * t is also a nonzero cube by nonzero_cubes_mul.
uses
pow_ne_zero,mul_ne_zero,subfield_nonzero_mem_cubes,nonzero_cubes_mul· obtain ⟨x, hx, hxa⟩ := ha have hacu : a ∈ nonzero_cubes E := ⟨x, hx, hxa⟩ have ha0 : a ≠ 0 := by rw [← hxa]; exact pow_ne_zero 3 hx have hat_ne : a * t ≠ 0 := mul_ne_zero ha0 ht have ht_cube : t ∈ nonzero_cubes E := subfield_nonzero_mem_cubes m hm t ht htq have hat_cube : a * t ∈ nonzero_cubes E := nonzero_cubes_mul hacu ht_cube
The trace of (a * t) * a⁻¹ from E to ZMod 2 is 0.
In the field E, (a * t) * a⁻¹ simplifies to t. Since t lies in the subfield F_{2^m} of E (satisfying t^(2^m) = t) and the field extension has degree 2m, subfield_element_trace_zero proves that its absolute trace is 0.
uses
subfield_element_trace_zerohave htrace : Algebra.trace (ZMod 2) E ((a * t) * a⁻¹) = 0 := by have h : (a * t) * a⁻¹ = t := by field_simp rw [h] exact subfield_element_trace_zero m hcard t htq
The component function for a * t is not bent, placing a * t in the non-bent components.
Because Tr((a * t) * a⁻¹) = 0, apn_family_fa_component_eq_cubic equates the component function x ↦ Tr((a * t) * apn_family_fa E a x) to the pure cubic power component x ↦ Tr((a * t) * x^3). Since a * t is a nonzero cube, cubic_power_component_cube_non_bent proves that this cubic power component is not bent, so a * t is a non-bent component by Or.inl.
uses
apn_family_fa_component_eq_cubic,cubic_power_component_cube_non_bent,Or.inlhave hfun : (fun x => Algebra.trace (ZMod 2) E ((a * t) * apn_family_fa E a x)) = (fun x => Algebra.trace (ZMod 2) E ((a * t) * x ^ 3)) := by funext x exact apn_family_fa_component_eq_cubic a (a * t) htrace x have hnb : ¬ is_field_bent E m (fun x => Algebra.trace (ZMod 2) E ((a * t) * apn_family_fa E a x)) := by rw [hfun] exact cubic_power_component_cube_non_bent m hcard (a * t) hat_cube exact Or.inl ⟨hat_ne, hnb⟩
The spread subspace is contained in non_bent_components E m a ∪ {0}.
Given β in the spread subspace, spread_line_contained_in_non_bent_mem_form shows β = a * t for some t with t^(2^m) = t. Then spread_line_contained_in_non_bent_gen applies to this t to conclude β ∈ non_bent_components E m a ∪ {0}.
uses
spread_line_contained_in_non_bent_mem_form,spread_line_contained_in_non_bent_genintro β hβ obtain ⟨t, htq, rfl⟩ := spread_line_contained_in_non_bent_mem_form m a hβ exact spread_line_contained_in_non_bent_gen m hm hcard a ha htq
charP_of_injective_algebraMap'- An algebra over a ring of characteristic p also has characteristic p when the algebra structure map is injective.
pow_ne_zero- In a reduced monoid with zero, any positive power of a nonzero element is nonzero.
Submodule.span_induction- To prove a property holds for every element in the submodule spanned by a set s, it suffices to prove it for generators in s, for 0, and that it is closed under addition and scalar multiplication.
zero_pow- Zero raised to any positive power is zero.
mul_zero- Multiplying any element by zero on the right gives zero.
add_pow_char_pow- In a commutative semiring of prime characteristic p, the Frobenius power satisfies (x + y)^(p^n) = x^(p^n) + y^(p^n).
mul_add- Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
map_pow- A monoid homomorphism preserves natural-number powers: f(a^n) = (f a)^n.
one_pow- One raised to any power is one.
mul_pow- In a commutative monoid, powers distribute over multiplication: (a * b)^n = a^n * b^n.
Algebra.smul_def- Scalar multiplication in an algebra is given by multiplication by the image of the scalar under the algebra map: r • x = (algebraMap R A) r * x.
eq_or_ne- Any two elements of a type are either equal or not equal.
mul_ne_zero- In a structure with no zero divisors, the product of two nonzero elements is nonzero.
subfield_nonzero_mem_cubes- When m is odd, every nonzero element of the subfield F_{2^m} in E (satisfying t^(2^m) = t) is a cube in E.
nonzero_cubes_mul- The product of two nonzero cubes in a field is a nonzero cube.
subfield_element_trace_zero- In a field of size 2^(2m), the absolute trace from E to ZMod 2 of any element in the subfield F_{2^m} is zero.
apn_family_fa_component_eq_cubic- If the trace of β * a⁻¹ is zero, the linear component Tr(β * f_a(x)) of the APN function f_a coincides with the pure cubic trace Tr(β * x^3).
cubic_power_component_cube_non_bent- If β is a nonzero cube in E, the cubic power trace component x ↦ Tr(β * x^3) is not bent.
Or.inl- From a proof of P, one can deduce P ∨ Q.
spread_line_contained_in_non_bent_mem_form- Every element β in the spread subspace spanned by a F_{2^m} can be written as a * t for some t with t^(2^m) = t.
spread_line_contained_in_non_bent_gen- For odd m and a nonzero cube a, any product a * t with t^(2^m) = t belongs to non_bent_components E m a ∪ {0}.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option linter.style.haveILetI false intheorem spread_line_contained_in_non_bent_mem_form {E : Type*} [Field E] [Algebra (ZMod 2) E] (m : ℕ) (a : E) {β : E} (hβ : β ∈ spread_subspace E m a) : ∃ t, t ^ (2^m) = t ∧ β = a * t := by haveI : CharP E 2 := charP_of_injective_algebraMap' (ZMod 2) 2 have hpow : 2^m ≠ 0 := pow_ne_zero m (by norm_num) unfold spread_subspace at hβ refine Submodule.span_induction (p := fun x _ => ∃ t, t ^ (2^m) = t ∧ x = a * t) ?_ ?_ ?_ ?_ hβ · rintro x ⟨t, ht, rfl⟩ exact ⟨t, ht, rfl⟩ · exact ⟨0, by rw [zero_pow hpow], by rw [mul_zero]⟩ · rintro x y _ _ ⟨tx, htx, rfl⟩ ⟨ty, hty, rfl⟩ exact ⟨tx + ty, by rw [add_pow_char_pow, htx, hty], by rw [mul_add]⟩ · rintro c x _ ⟨t, ht, rfl⟩ have hc : ((algebraMap (ZMod 2) E) c) ^ (2^m) = (algebraMap (ZMod 2) E) c := by rw [← map_pow] congr 1 fin_cases c · show (0 : ZMod 2) ^ (2^m) = 0 rw [zero_pow hpow] · show (1 : ZMod 2) ^ (2^m) = 1 rw [one_pow] refine ⟨(algebraMap (ZMod 2) E) c * t, ?_, ?_⟩ · rw [mul_pow, hc, ht] · rw [Algebra.smul_def]; ringset_option linter.style.haveILetI false intheorem spread_line_contained_in_non_bent_gen {E : Type*} [Field E] [Fintype E] [Algebra (ZMod 2) E] (m : ℕ) (hm : Odd m) (hcard : Fintype.card E = 2 ^ (2 * m)) (a : E) (ha : a ∈ nonzero_cubes E) {t : E} (htq : t ^ (2^m) = t) : a * t ∈ non_bent_components E m a ∪ {0} := by rcases eq_or_ne t 0 with rfl | ht · simp · obtain ⟨x, hx, hxa⟩ := ha have hacu : a ∈ nonzero_cubes E := ⟨x, hx, hxa⟩ have ha0 : a ≠ 0 := by rw [← hxa]; exact pow_ne_zero 3 hx have hat_ne : a * t ≠ 0 := mul_ne_zero ha0 ht have ht_cube : t ∈ nonzero_cubes E := subfield_nonzero_mem_cubes m hm t ht htq have hat_cube : a * t ∈ nonzero_cubes E := nonzero_cubes_mul hacu ht_cube have htrace : Algebra.trace (ZMod 2) E ((a * t) * a⁻¹) = 0 := by have h : (a * t) * a⁻¹ = t := by field_simp rw [h] exact subfield_element_trace_zero m hcard t htq have hfun : (fun x => Algebra.trace (ZMod 2) E ((a * t) * apn_family_fa E a x)) = (fun x => Algebra.trace (ZMod 2) E ((a * t) * x ^ 3)) := by funext x exact apn_family_fa_component_eq_cubic a (a * t) htrace x have hnb : ¬ is_field_bent E m (fun x => Algebra.trace (ZMod 2) E ((a * t) * apn_family_fa E a x)) := by rw [hfun] exact cubic_power_component_cube_non_bent m hcard (a * t) hat_cube exact Or.inl ⟨hat_ne, hnb⟩/-- For odd m and a in C, the spread line subspace a F_q is contained in N_{F_a} ∪ {0}. -/theorem spread_line_contained_in_non_bent {E : Type*} [Field E] [Fintype E] [Algebra (ZMod 2) E] (m : ℕ) (hm : Odd m) (hcard : Fintype.card E = 2 ^ (2 * m)) (a : E) (ha : a ∈ nonzero_cubes E) : (spread_subspace E m a : Set E) ⊆ non_bent_components E m a ∪ {0} := by intro β hβ obtain ⟨t, htq, rfl⟩ := spread_line_contained_in_non_bent_mem_form m a hβ exact spread_line_contained_in_non_bent_gen m hm hcard a ha htq