AFTD Auto-Formalizing Theoretical Domains

spread_line_contained_in_non_bent

theoremverifiedformalization

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.

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

    lines 5–8

    uses charP_of_injective_algebraMap', pow_ne_zero, Submodule.span_induction

      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β
  2. 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.

    lines 9–13

    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]⟩
  3. 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.

    lines 14–25

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

    lines 31–32

    uses eq_or_ne

      rcases eq_or_ne t 0 with rfl | ht
      · simp
  5. 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.

    lines 33–38

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

    lines 39–43

    uses subfield_element_trace_zero

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

    lines 44–51

    uses apn_family_fa_component_eq_cubic, cubic_power_component_cube_non_bent, Or.inl

        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⟩
  8. 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}.

    lines 55–57

    uses spread_line_contained_in_non_bent_mem_form, spread_line_contained_in_non_bent_gen

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

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
See it in the graphDiscuss this resultChallenge it