AFTD Auto-Formalizing Theoretical Domains

op_928_digit_exchange_differential_uniformity_le_thirty_six

theoremverifiedformalization

For every integer m ≥ 1 and every element c in GaloisField 2 m with absolute trace Algebra.trace (ZMod 2) (GaloisField 2 m) c = 1, the differential uniformity digit_exchange_differential_uniformity m c is at most 36.

Statement

theorem op_928_digit_exchange_differential_uniformity_le_thirty_six
    (m : ℕ) (hm : 1 ≤ m) (c : GaloisField 2 m)
    (hc : Algebra.trace (ZMod 2) (GaloisField 2 m) c = 1) :
    digit_exchange_differential_uniformity m c ≤ 36
Formalizes
arXiv:2611.02572, Theorem 1.1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

For any natural number $m \ge 1$ and any element $c \in \mathrm{GaloisField}(2, m)$ whose field trace from $\mathrm{GaloisField}(2, m)$ to $\mathbb{Z}/2\mathbb{Z}$ equals $1$, the "digit exchange differential uniformity" of $c$ (defined by digit_exchange_differential_uniformity m c) is at most $36$.

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

dummy

  1. The polynomial QP^2 - L'P * LP has degree 36. automation

    By substituting the polynomial expressions for W, DaP, DauP, bP, LP, L'P, and QP, the polynomial QP^2 - L'P * LP is simplified and its degree is computed by the compute_degree! tactic to be 36.

    lines 9–10

      subst hQ hL hL' hb hW hDa hDau
      compute_degree!
  2. The key squared equation holds.

    In characteristic 2, we rearrange the two equations E1 and E2 using linear_combination to isolate (L' * L)^N, and then square both sides and apply hN.

    lines 17–20

      have hQ : u * (L' ^ 2 + L' + c) + (β1 ^ 2 + β1) * a + L + β2 = (L' * L) ^ N := by
        linear_combination (-(β1 + L' + L + 1) * a) * E1 - E2 +
          (u * (L' ^ 2 + L' + c) + a * (L' ^ 2 + L' * L + L ^ 2 + L' + L + c) + L) * h2
      rw [hQ, hN]
  3. Squaring is injective and 0^N = 0.

    Because (s^2)^N = (s^N)^2 = s for all s, squaring is injective on F. Furthermore N is nonzero since 0 = (0^N)^2, so 0^N = 0.

    lines 35–41

    uses pow_mul, mul_comm, zero_pow

      have hsq : ∀ s t : F, s ^ 2 = t ^ 2 → s = t := by
        intro s t h
        have e : ∀ s : F, (s ^ 2) ^ N = s := fun s => by rw [← pow_mul, mul_comm, pow_mul, hN]
        rw [← e s, h, e t]
      have hN0 : N ≠ 0 := by
        intro h; have := hN 0; rw [h] at this; simp at this
      have h0N : (0:F) ^ N = 0 := zero_pow hN0
  4. Every solution satisfies the key squared identity.

    For each x in S, the defining equations of S match the hypotheses of op928_de_key with a = x.1, L = (x.1^2 + x.1 + c) * x.2, and L' = ((x.1 + u)^2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u)^N).

    lines 43–51

    uses op928_de_key

      have key : ∀ x ∈ S,
          (((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) + (x.1 ^ 2 + x.1 + c) * x.2 = β1 ∧
          (u * ((((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) ^ 2 +
            ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + c) + (β1 ^ 2 + β1) * x.1 +
            (x.1 ^ 2 + x.1 + c) * x.2 + β2) ^ 2 =
            (((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) * ((x.1 ^ 2 + x.1 + c) * x.2) := by
        intro x hx
        obtain ⟨E1, E2⟩ := hS x hx
        exact ⟨E1, op928_de_key h2 N hN c u β1 β2 x.1 _ _ E1 E2⟩
  5. When u = 0, the fiber has size at most 36.

    When u = 0, v is nonzero, and the first equation implies (x.1^2 + x.1 + c) * v = β1. Thus x.1 is a root of the degree-2 polynomial P(X) = v * (X^2 + X + c) - β1. Since x.1^2 + x.1 + c is nonzero and β1 is nonzero, x.2 is uniquely determined by x.1. Hence the projection x ↦ x.1 injects S into the roots of P, giving |S| ≤ 2 ≤ 36.

    lines 52–91

    uses add_zero, mul_zero, zero_mul, zero_add, Finset.card_le_card_of_injOn, Finset.mem_coe, Multiset.mem_toFinset, Polynomial.mem_roots, Polynomial.IsRoot.def, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_C, Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, mul_comm, sub_self, mul_ne_zero, mul_left_cancel₀, Prod.ext, Multiset.toFinset_card_le, Polynomial.card_roots'

      by_cases hu0 : u = 0
      · -- u = 0, v ≠ 0
        have hv : v ≠ 0 := fun hv => huv ⟨hu0, hv⟩
        subst hu0
        obtain ⟨P, hP⟩ : ∃ P : F[X], P = C v * (X ^ 2 + X + C c) - C β1 := ⟨_, rfl⟩
        have hPd : P.natDegree = 2 := by subst hP; compute_degree!
        have hP0 : P ≠ 0 := by intro h; rw [h] at hPd; simp at hPd
        have hdat : ∀ x ∈ S, (x.1 ^ 2 + x.1 + c) * v = β1 ∧
            β1 * ((x.1 ^ 2 + x.1 + c) * x.2) = ((β1 ^ 2 + β1) * x.1 + β2) ^ 2 := by
          intro x hx
          obtain ⟨E1, E2⟩ := key x hx
          simp only [add_zero, mul_zero, h0N, zero_mul, zero_add] at E1 E2
          have hE1 : (x.1 ^ 2 + x.1 + c) * v = β1 := by
            linear_combination E1 + (-(x.1 ^ 2 + x.1 + c) * x.2) * h2
          refine ⟨hE1, ?_⟩
          have hL' : (x.1 ^ 2 + x.1 + c) * (x.2 + v) = β1 - (x.1 ^ 2 + x.1 + c) * x.2 := by
            linear_combination E1
          rw [hL'] at E2
          linear_combination (-1) * E2 + (((x.1 ^ 2 + x.1 + c) * x.2) ^ 2 +
            ((x.1 ^ 2 + x.1 + c) * x.2) * ((β1 ^ 2 + β1) * x.1 + β2)) * h2
        calc S.card ≤ P.roots.toFinset.card := by
              apply Finset.card_le_card_of_injOn (fun x => x.1)
              · intro x hx
                rw [Finset.mem_coe, Multiset.mem_toFinset, mem_roots hP0, IsRoot.def, hP]
                simp only [eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]
                rw [mul_comm, (hdat x hx).1, sub_self]
              · intro x hx y hy hxy
                simp only at hxy
                have hb1 : β1 ≠ 0 := by
                  rw [← (hdat x hx).1]; exact mul_ne_zero (hD _) hv
                have h1 := (hdat x hx).2
                have h2' := (hdat y hy).2
                rw [hxy] at h1
                rw [← h2'] at h1
                have := mul_left_cancel₀ hb1 h1
                have := mul_left_cancel₀ (hD _) this
                exact Prod.ext hxy this
          _ ≤ P.roots.card := Multiset.toFinset_card_le _
          _ ≤ P.natDegree := card_roots' P
          _ ≤ 36 := by omega
  6. When u = 1, the fiber has size at most 36.

    When u = 1, (x.1 + 1)^2 + (x.1 + 1) + c = x.1^2 + x.1 + c in characteristic 2. Setting A = x.1^N, A is a root of a degree-5 polynomial P. For each of the at most 5 roots A, L = (x.1^2 + x.1 + c) * x.2 is a root of a degree-4 polynomial R(A). Since A determines x.1 and L determines x.2, S injects into the union of roots, giving |S| ≤ 5 * 4 = 20 ≤ 36.

    lines 92–152

    uses mul_one, one_mul, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_C, Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, Finset.card_le_card_of_injOn, Finset.mem_coe, Finset.mem_biUnion, Multiset.mem_toFinset, Polynomial.mem_roots, Polynomial.IsRoot.def, Finset.mem_image, Prod.mk.injEq, Prod.ext, mul_left_cancel₀, Finset.card_biUnion_le, Finset.sum_le_card_nsmul, Finset.card_image_le, Multiset.toFinset_card_le, Polynomial.card_roots', Nat.mul_le_mul_right

      by_cases hu1 : u = 1
      · subst hu1
        obtain ⟨P, hP⟩ : ∃ P : F[X], P = (X ^ 4 + X ^ 2 + C c) * (C v + X) - C β1 := ⟨_, rfl⟩
        have hPd : P.natDegree = 5 := by subst hP; compute_degree!
        have hP0 : P ≠ 0 := by intro h; rw [h] at hPd; simp at hPd
        let R : F → F[X] := fun A => (X ^ 2 + C (β1 ^ 2 + β1 + c + (β1 ^ 2 + β1) * A ^ 2 + β2)) ^ 2
          - (C β1 - X) * X
        have hRd : ∀ A, (R A).natDegree = 4 := by intro A; simp only [R]; compute_degree!
        have hR0 : ∀ A, R A ≠ 0 := by intro A h; have := hRd A; rw [h] at this; simp at this
        have hdat : ∀ x ∈ S, eval (x.1 ^ N) P = 0 ∧
            eval ((x.1 ^ 2 + x.1 + c) * x.2) (R (x.1 ^ N)) = 0 := by
          intro x hx
          obtain ⟨E1, E2⟩ := key x hx
          simp only [mul_one, one_mul] at E1 E2
          have ha := hN x.1
          constructor
          · rw [hP]
            simp only [eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]
            rw [show (x.1 ^ N) ^ 4 = ((x.1 ^ N) ^ 2) ^ 2 by ring, ha]
            linear_combination E1 + (-((x.1 ^ 2 + x.1 + c) * x.2) -
              (x.1 + 1) * (x.2 + v + x.1 ^ N)) * h2
          · have hL' : ((x.1 + 1) ^ 2 + (x.1 + 1) + c) * (x.2 + v + x.1 ^ N) =
                β1 - (x.1 ^ 2 + x.1 + c) * x.2 := by linear_combination E1
            rw [hL'] at E2
            simp only [R, eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]
            rw [ha]
            linear_combination E2 + (β1 * ((x.1 ^ 2 + x.1 + c) * x.2) *
              (((x.1 ^ 2 + x.1 + c) * x.2) ^ 2 + (β1 ^ 2 + β1 + c + (β1 ^ 2 + β1) * x.1 + β2) +
                (((β1 - (x.1 ^ 2 + x.1 + c) * x.2) ^ 2 + (β1 - (x.1 ^ 2 + x.1 + c) * x.2) + c) +
                  (β1 ^ 2 + β1) * x.1 + (x.1 ^ 2 + x.1 + c) * x.2 + β2))) * h2
        calc S.card ≤ (P.roots.toFinset.biUnion
              (fun A => (R A).roots.toFinset.image (fun L => (A, L)))).card := by
              apply Finset.card_le_card_of_injOn (fun x => (x.1 ^ N, (x.1 ^ 2 + x.1 + c) * x.2))
              · intro x hx
                rw [Finset.mem_coe, Finset.mem_biUnion]
                refine ⟨x.1 ^ N, ?_, ?_⟩
                · rw [Multiset.mem_toFinset, mem_roots hP0, IsRoot.def]; exact (hdat x hx).1
                · rw [Finset.mem_image]
                  refine ⟨(x.1 ^ 2 + x.1 + c) * x.2, ?_, rfl⟩
                  rw [Multiset.mem_toFinset, mem_roots (hR0 _), IsRoot.def]; exact (hdat x hx).2
              · intro x _ y _ hxy
                simp only [Prod.mk.injEq] at hxy
                have h1 : x.1 = y.1 := by rw [← hN x.1, ← hN y.1, hxy.1]
                have h3 := hxy.2
                rw [h1] at h3
                exact Prod.ext h1 (mul_left_cancel₀ (hD _) h3)
          _ ≤ ∑ A ∈ P.roots.toFinset, ((R A).roots.toFinset.image (fun L => (A, L))).card :=
              Finset.card_biUnion_le
          _ ≤ P.roots.toFinset.card • 4 := by
              apply Finset.sum_le_card_nsmul
              intro A _
              calc _ ≤ (R A).roots.toFinset.card := Finset.card_image_le
                _ ≤ (R A).roots.card := Multiset.toFinset_card_le _
                _ ≤ (R A).natDegree := card_roots' _
                _ = 4 := hRd A
          _ ≤ 5 • 4 := by
              apply Nat.mul_le_mul_right
              calc _ ≤ P.roots.card := Multiset.toFinset_card_le _
                _ ≤ P.natDegree := card_roots' _
                _ = 5 := hPd
          _ ≤ 36 := by norm_num
  7. In the generic case, the fiber has size at most 36.

    When u is neither 0 nor 1, setting σ = u^N and κ = u^2 + u ≠ 0 allows expressing x.2 as a polynomial bP in A = x.1^N. Then L = LP(A) and L' = L'P(A), and the key identity shows A is a root of QP^2 - L'P * LP. By op928_de_poly36_natDegree, this polynomial has degree 36. Since A determines x.1 and then x.2, the projection x ↦ x.1^N injects S into its roots, so |S| ≤ 36.

    lines 154–218

    uses op928_de_poly36_natDegree, mul_pow, Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C, Polynomial.eval_mul, Polynomial.eval_sub, Finset.card_le_card_of_injOn, Finset.mem_coe, Multiset.mem_toFinset, Polynomial.mem_roots, Polynomial.IsRoot.def, Prod.ext, mul_left_cancel₀, Multiset.toFinset_card_le, Polynomial.card_roots'

      set σ := u ^ N with hσdef
      have hσ : σ ≠ 0 := by intro h; apply hu0; rw [← hN u, ← hσdef, h]; ring
      set κ := u ^ 2 + u with hκdef
      have hκ : κ ≠ 0 := by
        rw [hκdef, show u ^ 2 + u = u * (u + 1) by ring]
        refine mul_ne_zero hu0 ?_
        intro h; apply hu1; linear_combination h - h2
      obtain ⟨W, hW⟩ : ∃ W : F[X], W = C v + C σ * X := ⟨_, rfl⟩
      obtain ⟨DaP, hDa⟩ : ∃ DaP : F[X], DaP = X ^ 4 + X ^ 2 + C c := ⟨_, rfl⟩
      obtain ⟨DauP, hDau⟩ : ∃ DauP : F[X], DauP = (X ^ 2 + C u) ^ 2 + (X ^ 2 + C u) + C c := ⟨_, rfl⟩
      obtain ⟨bP, hb⟩ : ∃ bP : F[X], bP = C κ⁻¹ * (C β1 + DauP * W) := ⟨_, rfl⟩
      obtain ⟨LP, hL⟩ : ∃ LP : F[X], LP = DaP * bP := ⟨_, rfl⟩
      obtain ⟨L'P, hL'⟩ : ∃ L'P : F[X], L'P = DauP * (bP + W) := ⟨_, rfl⟩
      obtain ⟨QP, hQ⟩ : ∃ QP : F[X],
        QP = C u * (L'P ^ 2 + L'P + C c) + C (β1 ^ 2 + β1) * X ^ 2 + LP + C β2 := ⟨_, rfl⟩
      have hPd := op928_de_poly36_natDegree u v σ c β1 β2 κ hu0 hσ hκ W DaP DauP bP LP L'P QP
        hW hDa hDau hb hL hL' hQ
      have hP0 : QP ^ 2 - L'P * LP ≠ 0 := by intro h; rw [h] at hPd; simp at hPd
      have hbx : ∀ x ∈ S, κ * x.2 = β1 + ((x.1 + u) ^ 2 + (x.1 + u) + c) * (v + x.1 ^ N * σ) := by
        intro x hx
        obtain ⟨E1, _⟩ := key x hx
        rw [mul_pow] at E1
        linear_combination E1 + (-((x.1 + u) ^ 2 + (x.1 + u) + c) * (v + x.1 ^ N * σ) -
          (x.1 ^ 2 + x.1 + c) * x.2 - x.1 * u * x.2) * h2
      have hroot : ∀ x ∈ S, eval (x.1 ^ N) (QP ^ 2 - L'P * LP) = 0 := by
        intro x hx
        obtain ⟨_, E2⟩ := key x hx
        have ha := hN x.1
        set A := x.1 ^ N with hA
        have eDa : eval A DaP = x.1 ^ 2 + x.1 + c := by
          rw [hDa]; simp only [eval_add, eval_pow, eval_X, eval_C]
          rw [show A ^ 4 = (A ^ 2) ^ 2 by ring, ha]
        have eDau : eval A DauP = (x.1 + u) ^ 2 + (x.1 + u) + c := by
          rw [hDau]; simp only [eval_add, eval_pow, eval_X, eval_C]; rw [ha]
        have eW : eval A W = v + A * σ := by
          rw [hW]; simp only [eval_add, eval_mul, eval_X, eval_C]; ring
        have eb : eval A bP = x.2 := by
          rw [hb]; simp only [eval_add, eval_mul, eval_C]
          rw [eDau, eW, ← hbx x hx]
          field_simp
        have eL : eval A LP = (x.1 ^ 2 + x.1 + c) * x.2 := by
          rw [hL, eval_mul, eDa, eb]
        have eL' : eval A L'P = ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) := by
          rw [hL', eval_mul, eval_add, eDau, eb, eW, mul_pow, ← hσdef]; ring
        have eQ : eval A QP = u * ((((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) ^ 2 +
            ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + c) + (β1 ^ 2 + β1) * x.1 +
            (x.1 ^ 2 + x.1 + c) * x.2 + β2 := by
          rw [hQ]; simp only [eval_add, eval_mul, eval_pow, eval_X, eval_C]
          rw [eL', eL, ha]
        rw [eval_sub, eval_pow, eval_mul, eQ, eL', eL, E2, sub_self]
      calc S.card ≤ (QP ^ 2 - L'P * LP).roots.toFinset.card := by
            apply Finset.card_le_card_of_injOn (fun x => x.1 ^ N)
            · intro x hx
              rw [Finset.mem_coe, Multiset.mem_toFinset, mem_roots hP0, IsRoot.def]
              exact hroot x hx
            · intro x hx y hy hxy
              simp only at hxy
              have h1 : x.1 = y.1 := by rw [← hN x.1, ← hN y.1, hxy]
              have h3 := hbx x hx
              rw [h1, ← hbx y hy] at h3
              exact Prod.ext h1 (mul_left_cancel₀ hκ h3)
        _ ≤ (QP ^ 2 - L'P * LP).roots.card := Multiset.toFinset_card_le _
        _ ≤ (QP ^ 2 - L'P * LP).natDegree := card_roots' _
        _ = 36 := hPd
    
  8. The trace of x^2 + x is zero.

    The squaring map is the Frobenius algebra automorphism over ZMod 2, so the trace of x^2 equals the trace of x. By linearity and characteristic 2, the trace of x^2 + x is zero.

    lines 221–232

    uses Fintype.ofFinite, ExpChar.prime, Nat.prime_two, FiniteField.frobeniusAlgEquiv, FiniteField.frobeniusAlgHom, FiniteField.coe_frobeniusAlgHom, ZMod.card, Algebra.trace_eq_of_algEquiv, map_add, CharTwo.add_self_eq_zero

      have : Fintype (GaloisField 2 m) := Fintype.ofFinite (GaloisField 2 m)
      have : ExpChar (GaloisField 2 m) 2 := ExpChar.prime Nat.prime_two
      have h1 : (FiniteField.frobeniusAlgEquiv (ZMod 2) (GaloisField 2 m) 2) x = x ^ 2 := by
        change FiniteField.frobeniusAlgHom (ZMod 2) (GaloisField 2 m) x = x ^ 2
        rw [FiniteField.coe_frobeniusAlgHom]
        change x ^ Fintype.card (ZMod 2) = x ^ 2
        rw [ZMod.card]
      have h2 : Algebra.trace (ZMod 2) (GaloisField 2 m) (x ^ 2) =
          Algebra.trace (ZMod 2) (GaloisField 2 m) x := by
        rw [← h1, Algebra.trace_eq_of_algEquiv]
      rw [map_add, h2]
      exact CharTwo.add_self_eq_zero _
  9. x^2 + x + c is never zero for trace-one c.

    If x^2 + x + c = 0, taking the trace gives 0 = Tr(x^2 + x + c) = Tr(x^2 + x) + Tr(c) = 0 + 1 = 1, a contradiction.

    lines 239–247

    uses map_zero, map_add, op928_de_trace_sq_add_self, zero_add

      classical
      have hD : ∀ x : GaloisField 2 m, x ^ 2 + x + c ≠ 0 := by
        intro x h
        have htr : Algebra.trace (ZMod 2) (GaloisField 2 m) (x ^ 2 + x + c) = 0 := by
          rw [h, map_zero]
        rw [map_add, op928_de_trace_sq_add_self, zero_add, hc] at htr
        revert htr
        decide
      have h2 : (2 : GaloisField 2 m) = 0 := CharTwo.two_eq_zero
  10. The differential uniformity is at most 36.

    The differential uniformity is the supremum of fiber sizes over nonzero (u, v) and all (β1, β2). For N = 2^(m-1), Fermat's Little Theorem gives (t^N)^2 = t. Applying op928_de_fiber_le to each fiber gives size at most 36, so the supremum is at most 36.

    lines 248–269

    uses CharTwo.two_eq_zero, Finset.sup_le, pow_mul, pow_succ, Nat.card_eq_fintype_card, GaloisField.card, FiniteField.pow_card, Fintype.ofFinite, op928_de_fiber_le, Finset.mem_filter, Prod.mk.injEq

      unfold digit_exchange_differential_uniformity
      simp only
      apply Finset.sup_le
      rintro ⟨u, v⟩ huv
      apply Finset.sup_le
      rintro ⟨β1, β2⟩ _
      have hN : ∀ t : GaloisField 2 m, (t ^ (2 ^ (m - 1))) ^ 2 = t := by
        intro t
        let _ : Fintype (GaloisField 2 m) := Fintype.ofFinite _
        rw [← pow_mul, ← pow_succ, show m - 1 + 1 = m by omega]
        have hcard : Fintype.card (GaloisField 2 m) = 2 ^ m := by
          rw [← Nat.card_eq_fintype_card, ← GaloisField.card 2 m (by omega), Nat.card_eq_fintype_card]
        rw [← hcard]
        exact FiniteField.pow_card t
      have huv' : ¬ (u = 0 ∧ v = 0) := by
        rintro ⟨rfl, rfl⟩
        simp at huv
      letI : Fintype (GaloisField 2 m) := Fintype.ofFinite _
      apply op928_de_fiber_le h2 (2 ^ (m - 1)) hN c hD u v β1 β2 huv'
      intro x hx
      rw [Finset.mem_filter] at hx
      simpa only [Prod.mk.injEq] using hx.2
FiniteField.coe_frobeniusAlgHom
Squaring is the Frobenius endomorphism over ZMod 2

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

open Polynomial intheorem op928_de_poly36_natDegree {F : Type*} [Field F] (u v σ c β1 β2 κ : F)    (hu : u ≠ 0) (hσ : σ ≠ 0) (hκ : κ ≠ 0) (W DaP DauP bP LP L'P QP : F[X])    (hW : W = C v + C σ * X) (hDa : DaP = X ^ 4 + X ^ 2 + C c)    (hDau : DauP = (X ^ 2 + C u) ^ 2 + (X ^ 2 + C u) + C c)    (hb : bP = C κ⁻¹ * (C β1 + DauP * W)) (hL : LP = DaP * bP) (hL' : L'P = DauP * (bP + W))    (hQ : QP = C u * (L'P ^ 2 + L'P + C c) + C (β1 ^ 2 + β1) * X ^ 2 + LP + C β2) :    (QP ^ 2 - L'P * LP).natDegree = 36 := by  subst hQ hL hL' hb hW hDa hDau  compute_degree!theorem op928_de_key {F : Type*} [Field F] (h2 : (2:F) = 0) (N : ℕ) (hN : ∀ t : F, (t ^ N) ^ 2 = t)    (c u β1 β2 a L L' : F)    (E1 : L' + L = β1)    (E2 : (L' ^ 2 + L' + c) * (a + u) + L + (L ^ 2 + L + c) * a + (L' * L) ^ N = β2) :    (u * (L' ^ 2 + L' + c) + (β1 ^ 2 + β1) * a + L + β2) ^ 2 = L' * L := by  have hQ : u * (L' ^ 2 + L' + c) + (β1 ^ 2 + β1) * a + L + β2 = (L' * L) ^ N := by    linear_combination (-(β1 + L' + L + 1) * a) * E1 - E2 +      (u * (L' ^ 2 + L' + c) + a * (L' ^ 2 + L' * L + L ^ 2 + L' + L + c) + L) * h2  rw [hQ, hN]open Polynomial intheorem op928_de_fiber_le {F : Type*} [Field F] [Fintype F] [DecidableEq F] (h2 : (2:F) = 0) (N : ℕ)    (hN : ∀ t : F, (t ^ N) ^ 2 = t) (c : F) (hD : ∀ t : F, t ^ 2 + t + c ≠ 0)    (u v β1 β2 : F) (huv : ¬ (u = 0 ∧ v = 0)) (S : Finset (F × F))    (hS : ∀ x ∈ S,      ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + (x.1 ^ 2 + x.1 + c) * x.2 = β1 ∧      ((((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) ^ 2 +        ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + c) * (x.1 + u) +        (x.1 ^ 2 + x.1 + c) * x.2 +        (((x.1 ^ 2 + x.1 + c) * x.2) ^ 2 + (x.1 ^ 2 + x.1 + c) * x.2 + c) * x.1 +        (((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) * ((x.1 ^ 2 + x.1 + c) * x.2)) ^ N        = β2) :    S.card ≤ 36 := by  have hsq : ∀ s t : F, s ^ 2 = t ^ 2 → s = t := by    intro s t h    have e : ∀ s : F, (s ^ 2) ^ N = s := fun s => by rw [← pow_mul, mul_comm, pow_mul, hN]    rw [← e s, h, e t]  have hN0 : N ≠ 0 := by    intro h; have := hN 0; rw [h] at this; simp at this  have h0N : (0:F) ^ N = 0 := zero_pow hN0  -- consequences for one solution  have key : ∀ x ∈ S,      (((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) + (x.1 ^ 2 + x.1 + c) * x.2 = β1 ∧      (u * ((((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) ^ 2 +        ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + c) + (β1 ^ 2 + β1) * x.1 +        (x.1 ^ 2 + x.1 + c) * x.2 + β2) ^ 2 =        (((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) * ((x.1 ^ 2 + x.1 + c) * x.2) := by    intro x hx    obtain ⟨E1, E2⟩ := hS x hx    exact ⟨E1, op928_de_key h2 N hN c u β1 β2 x.1 _ _ E1 E2⟩  by_cases hu0 : u = 0  · -- u = 0, v ≠ 0    have hv : v ≠ 0 := fun hv => huv ⟨hu0, hv⟩    subst hu0    obtain ⟨P, hP⟩ : ∃ P : F[X], P = C v * (X ^ 2 + X + C c) - C β1 := ⟨_, rfl⟩    have hPd : P.natDegree = 2 := by subst hP; compute_degree!    have hP0 : P ≠ 0 := by intro h; rw [h] at hPd; simp at hPd    have hdat : ∀ x ∈ S, (x.1 ^ 2 + x.1 + c) * v = β1 ∧        β1 * ((x.1 ^ 2 + x.1 + c) * x.2) = ((β1 ^ 2 + β1) * x.1 + β2) ^ 2 := by      intro x hx      obtain ⟨E1, E2⟩ := key x hx      simp only [add_zero, mul_zero, h0N, zero_mul, zero_add] at E1 E2      have hE1 : (x.1 ^ 2 + x.1 + c) * v = β1 := by        linear_combination E1 + (-(x.1 ^ 2 + x.1 + c) * x.2) * h2      refine ⟨hE1, ?_⟩      have hL' : (x.1 ^ 2 + x.1 + c) * (x.2 + v) = β1 - (x.1 ^ 2 + x.1 + c) * x.2 := by        linear_combination E1      rw [hL'] at E2      linear_combination (-1) * E2 + (((x.1 ^ 2 + x.1 + c) * x.2) ^ 2 +        ((x.1 ^ 2 + x.1 + c) * x.2) * ((β1 ^ 2 + β1) * x.1 + β2)) * h2    calc S.card ≤ P.roots.toFinset.card := by          apply Finset.card_le_card_of_injOn (fun x => x.1)          · intro x hx            rw [Finset.mem_coe, Multiset.mem_toFinset, mem_roots hP0, IsRoot.def, hP]            simp only [eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]            rw [mul_comm, (hdat x hx).1, sub_self]          · intro x hx y hy hxy            simp only at hxy            have hb1 : β1 ≠ 0 := by              rw [← (hdat x hx).1]; exact mul_ne_zero (hD _) hv            have h1 := (hdat x hx).2            have h2' := (hdat y hy).2            rw [hxy] at h1            rw [← h2'] at h1            have := mul_left_cancel₀ hb1 h1            have := mul_left_cancel₀ (hD _) this            exact Prod.ext hxy this      _ ≤ P.roots.card := Multiset.toFinset_card_le _      _ ≤ P.natDegree := card_roots' P      _ ≤ 36 := by omega  by_cases hu1 : u = 1  · subst hu1    obtain ⟨P, hP⟩ : ∃ P : F[X], P = (X ^ 4 + X ^ 2 + C c) * (C v + X) - C β1 := ⟨_, rfl⟩    have hPd : P.natDegree = 5 := by subst hP; compute_degree!    have hP0 : P ≠ 0 := by intro h; rw [h] at hPd; simp at hPd    let R : F → F[X] := fun A => (X ^ 2 + C (β1 ^ 2 + β1 + c + (β1 ^ 2 + β1) * A ^ 2 + β2)) ^ 2      - (C β1 - X) * X    have hRd : ∀ A, (R A).natDegree = 4 := by intro A; simp only [R]; compute_degree!    have hR0 : ∀ A, R A ≠ 0 := by intro A h; have := hRd A; rw [h] at this; simp at this    have hdat : ∀ x ∈ S, eval (x.1 ^ N) P = 0 ∧        eval ((x.1 ^ 2 + x.1 + c) * x.2) (R (x.1 ^ N)) = 0 := by      intro x hx      obtain ⟨E1, E2⟩ := key x hx      simp only [mul_one, one_mul] at E1 E2      have ha := hN x.1      constructor      · rw [hP]        simp only [eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]        rw [show (x.1 ^ N) ^ 4 = ((x.1 ^ N) ^ 2) ^ 2 by ring, ha]        linear_combination E1 + (-((x.1 ^ 2 + x.1 + c) * x.2) -          (x.1 + 1) * (x.2 + v + x.1 ^ N)) * h2      · have hL' : ((x.1 + 1) ^ 2 + (x.1 + 1) + c) * (x.2 + v + x.1 ^ N) =            β1 - (x.1 ^ 2 + x.1 + c) * x.2 := by linear_combination E1        rw [hL'] at E2        simp only [R, eval_sub, eval_mul, eval_C, eval_add, eval_pow, eval_X]        rw [ha]        linear_combination E2 + (β1 * ((x.1 ^ 2 + x.1 + c) * x.2) *          (((x.1 ^ 2 + x.1 + c) * x.2) ^ 2 + (β1 ^ 2 + β1 + c + (β1 ^ 2 + β1) * x.1 + β2) +            (((β1 - (x.1 ^ 2 + x.1 + c) * x.2) ^ 2 + (β1 - (x.1 ^ 2 + x.1 + c) * x.2) + c) +              (β1 ^ 2 + β1) * x.1 + (x.1 ^ 2 + x.1 + c) * x.2 + β2))) * h2    calc S.card ≤ (P.roots.toFinset.biUnion          (fun A => (R A).roots.toFinset.image (fun L => (A, L)))).card := by          apply Finset.card_le_card_of_injOn (fun x => (x.1 ^ N, (x.1 ^ 2 + x.1 + c) * x.2))          · intro x hx            rw [Finset.mem_coe, Finset.mem_biUnion]            refine ⟨x.1 ^ N, ?_, ?_⟩            · rw [Multiset.mem_toFinset, mem_roots hP0, IsRoot.def]; exact (hdat x hx).1            · rw [Finset.mem_image]              refine ⟨(x.1 ^ 2 + x.1 + c) * x.2, ?_, rfl⟩              rw [Multiset.mem_toFinset, mem_roots (hR0 _), IsRoot.def]; exact (hdat x hx).2          · intro x _ y _ hxy            simp only [Prod.mk.injEq] at hxy            have h1 : x.1 = y.1 := by rw [← hN x.1, ← hN y.1, hxy.1]            have h3 := hxy.2            rw [h1] at h3            exact Prod.ext h1 (mul_left_cancel₀ (hD _) h3)      _ ≤ ∑ A ∈ P.roots.toFinset, ((R A).roots.toFinset.image (fun L => (A, L))).card :=          Finset.card_biUnion_le      _ ≤ P.roots.toFinset.card • 4 := by          apply Finset.sum_le_card_nsmul          intro A _          calc _ ≤ (R A).roots.toFinset.card := Finset.card_image_le            _ ≤ (R A).roots.card := Multiset.toFinset_card_le _            _ ≤ (R A).natDegree := card_roots' _            _ = 4 := hRd A      _ ≤ 5 • 4 := by          apply Nat.mul_le_mul_right          calc _ ≤ P.roots.card := Multiset.toFinset_card_le _            _ ≤ P.natDegree := card_roots' _            _ = 5 := hPd      _ ≤ 36 := by norm_num  -- generic case  set σ := u ^ N with hσdef  have hσ : σ ≠ 0 := by intro h; apply hu0; rw [← hN u, ← hσdef, h]; ring  set κ := u ^ 2 + u with hκdef  have hκ : κ ≠ 0 := by    rw [hκdef, show u ^ 2 + u = u * (u + 1) by ring]    refine mul_ne_zero hu0 ?_    intro h; apply hu1; linear_combination h - h2  obtain ⟨W, hW⟩ : ∃ W : F[X], W = C v + C σ * X := ⟨_, rfl⟩  obtain ⟨DaP, hDa⟩ : ∃ DaP : F[X], DaP = X ^ 4 + X ^ 2 + C c := ⟨_, rfl⟩  obtain ⟨DauP, hDau⟩ : ∃ DauP : F[X], DauP = (X ^ 2 + C u) ^ 2 + (X ^ 2 + C u) + C c := ⟨_, rfl⟩  obtain ⟨bP, hb⟩ : ∃ bP : F[X], bP = C κ⁻¹ * (C β1 + DauP * W) := ⟨_, rfl⟩  obtain ⟨LP, hL⟩ : ∃ LP : F[X], LP = DaP * bP := ⟨_, rfl⟩  obtain ⟨L'P, hL'⟩ : ∃ L'P : F[X], L'P = DauP * (bP + W) := ⟨_, rfl⟩  obtain ⟨QP, hQ⟩ : ∃ QP : F[X],    QP = C u * (L'P ^ 2 + L'P + C c) + C (β1 ^ 2 + β1) * X ^ 2 + LP + C β2 := ⟨_, rfl⟩  have hPd := op928_de_poly36_natDegree u v σ c β1 β2 κ hu0 hσ hκ W DaP DauP bP LP L'P QP    hW hDa hDau hb hL hL' hQ  have hP0 : QP ^ 2 - L'P * LP ≠ 0 := by intro h; rw [h] at hPd; simp at hPd  have hbx : ∀ x ∈ S, κ * x.2 = β1 + ((x.1 + u) ^ 2 + (x.1 + u) + c) * (v + x.1 ^ N * σ) := by    intro x hx    obtain ⟨E1, _⟩ := key x hx    rw [mul_pow] at E1    linear_combination E1 + (-((x.1 + u) ^ 2 + (x.1 + u) + c) * (v + x.1 ^ N * σ) -      (x.1 ^ 2 + x.1 + c) * x.2 - x.1 * u * x.2) * h2  have hroot : ∀ x ∈ S, eval (x.1 ^ N) (QP ^ 2 - L'P * LP) = 0 := by    intro x hx    obtain ⟨_, E2⟩ := key x hx    have ha := hN x.1    set A := x.1 ^ N with hA    have eDa : eval A DaP = x.1 ^ 2 + x.1 + c := by      rw [hDa]; simp only [eval_add, eval_pow, eval_X, eval_C]      rw [show A ^ 4 = (A ^ 2) ^ 2 by ring, ha]    have eDau : eval A DauP = (x.1 + u) ^ 2 + (x.1 + u) + c := by      rw [hDau]; simp only [eval_add, eval_pow, eval_X, eval_C]; rw [ha]    have eW : eval A W = v + A * σ := by      rw [hW]; simp only [eval_add, eval_mul, eval_X, eval_C]; ring    have eb : eval A bP = x.2 := by      rw [hb]; simp only [eval_add, eval_mul, eval_C]      rw [eDau, eW, ← hbx x hx]      field_simp    have eL : eval A LP = (x.1 ^ 2 + x.1 + c) * x.2 := by      rw [hL, eval_mul, eDa, eb]    have eL' : eval A L'P = ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) := by      rw [hL', eval_mul, eval_add, eDau, eb, eW, mul_pow, ← hσdef]; ring    have eQ : eval A QP = u * ((((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N)) ^ 2 +        ((x.1 + u) ^ 2 + (x.1 + u) + c) * (x.2 + v + (x.1 * u) ^ N) + c) + (β1 ^ 2 + β1) * x.1 +        (x.1 ^ 2 + x.1 + c) * x.2 + β2 := by      rw [hQ]; simp only [eval_add, eval_mul, eval_pow, eval_X, eval_C]      rw [eL', eL, ha]    rw [eval_sub, eval_pow, eval_mul, eQ, eL', eL, E2, sub_self]  calc S.card ≤ (QP ^ 2 - L'P * LP).roots.toFinset.card := by        apply Finset.card_le_card_of_injOn (fun x => x.1 ^ N)        · intro x hx          rw [Finset.mem_coe, Multiset.mem_toFinset, mem_roots hP0, IsRoot.def]          exact hroot x hx        · intro x hx y hy hxy          simp only at hxy          have h1 : x.1 = y.1 := by rw [← hN x.1, ← hN y.1, hxy]          have h3 := hbx x hx          rw [h1, ← hbx y hy] at h3          exact Prod.ext h1 (mul_left_cancel₀ hκ h3)    _ ≤ (QP ^ 2 - L'P * LP).roots.card := Multiset.toFinset_card_le _    _ ≤ (QP ^ 2 - L'P * LP).natDegree := card_roots' _    _ = 36 := hPdtheorem op928_de_trace_sq_add_self (m : ℕ) (x : GaloisField 2 m) :    Algebra.trace (ZMod 2) (GaloisField 2 m) (x ^ 2 + x) = 0 := by  have : Fintype (GaloisField 2 m) := Fintype.ofFinite (GaloisField 2 m)  have : ExpChar (GaloisField 2 m) 2 := ExpChar.prime Nat.prime_two  have h1 : (FiniteField.frobeniusAlgEquiv (ZMod 2) (GaloisField 2 m) 2) x = x ^ 2 := by    change FiniteField.frobeniusAlgHom (ZMod 2) (GaloisField 2 m) x = x ^ 2    rw [FiniteField.coe_frobeniusAlgHom]    change x ^ Fintype.card (ZMod 2) = x ^ 2    rw [ZMod.card]  have h2 : Algebra.trace (ZMod 2) (GaloisField 2 m) (x ^ 2) =      Algebra.trace (ZMod 2) (GaloisField 2 m) x := by    rw [← h1, Algebra.trace_eq_of_algEquiv]  rw [map_add, h2]  exact CharTwo.add_self_eq_zero _/-- Theorem 1.1 of arXiv:2611.02572: the differential uniformity of G_c is at most 36 for all m ≥ 1 and all trace-one c. -/theorem op_928_digit_exchange_differential_uniformity_le_thirty_six    (m : ℕ) (hm : 1 ≤ m) (c : GaloisField 2 m)    (hc : Algebra.trace (ZMod 2) (GaloisField 2 m) c = 1) :    digit_exchange_differential_uniformity m c ≤ 36 := by  classical  have hD : ∀ x : GaloisField 2 m, x ^ 2 + x + c ≠ 0 := by    intro x h    have htr : Algebra.trace (ZMod 2) (GaloisField 2 m) (x ^ 2 + x + c) = 0 := by      rw [h, map_zero]    rw [map_add, op928_de_trace_sq_add_self, zero_add, hc] at htr    revert htr    decide  have h2 : (2 : GaloisField 2 m) = 0 := CharTwo.two_eq_zero  unfold digit_exchange_differential_uniformity  simp only  apply Finset.sup_le  rintro ⟨u, v⟩ huv  apply Finset.sup_le  rintro ⟨β1, β2⟩ _  have hN : ∀ t : GaloisField 2 m, (t ^ (2 ^ (m - 1))) ^ 2 = t := by    intro t    let _ : Fintype (GaloisField 2 m) := Fintype.ofFinite _    rw [← pow_mul, ← pow_succ, show m - 1 + 1 = m by omega]    have hcard : Fintype.card (GaloisField 2 m) = 2 ^ m := by      rw [← Nat.card_eq_fintype_card, ← GaloisField.card 2 m (by omega), Nat.card_eq_fintype_card]    rw [← hcard]    exact FiniteField.pow_card t  have huv' : ¬ (u = 0 ∧ v = 0) := by    rintro ⟨rfl, rfl⟩    simp at huv  letI : Fintype (GaloisField 2 m) := Fintype.ofFinite _  apply op928_de_fiber_le h2 (2 ^ (m - 1)) hN c hD u v β1 β2 huv'  intro x hx  rw [Finset.mem_filter] at hx  simpa only [Prod.mk.injEq] using hx.2
See it in the graphDiscuss this resultChallenge it