AFTD Auto-Formalizing Theoretical Domains

op_928_digit_exchange_differential_uniformity_ge_two

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

Statement

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

Read back from the Lean

For every natural number $m$ such that $1 \le m$, and every element $c$ of the Galois field $\mathbb{F}_{2^m}$ whose field trace to $\mathbb{Z}/2\mathbb{Z}$ is $1$ (i.e., $\operatorname{Tr}_{\mathbb{F}_{2^m}/\mathbb{F}_2}(c) = 1$), the digit-exchange differential uniformity of $c$ (defined as digit_exchange_differential_uniformity m c) is at least $2$.

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 differential uniformity of the digit-exchange permutation is defined as the supremum, over all non-zero input differences $\alpha$ and all output differences $\beta$, of the number of solutions to the differential equation $\operatorname{sub}(G(\operatorname{add}(x, \alpha)), G(x)) = \beta$. The proof establishes that this supremum is at least 2 by picking the specific differences $\alpha = (0, 1)$ and $\beta = (c, 0)$ and exhibiting two distinct solutions: $x_1 = (0, 0)$ and $x_2 = (1, (c+1)^2)$. Verifying these solutions relies on characteristic-2 polynomial arithmetic and the finite field Frobenius identity $(y^2)^{2^{m-1}} = y$. Since the two solutions form a two-element subset of the solution set, the solution count is at least 2, providing the required lower bound on the supremum.

  1. In $\mathbb{F}_{2^m}$, characteristic 2 holds ($2 = 0$), the field size is $2^m$, and $(y^2)^{2^{m-1}} = y$ for all elements $y$.

    Since the base characteristic is 2, the element 2 vanishes ($2 = 0$). With $m \ge 1$, the field size is $2^m$, so Fermat's little theorem for finite fields (`FiniteField.pow_card`) gives $y^{2^m} = y$. Factoring the exponent as $2 \cdot 2^{m-1} = 2^m$ yields $(y^2)^{2^{m-1}} = y$. We also note that $2^{m-1} \ne 0$.

    lines 6–17

    uses Fintype.ofFinite, Nat.prime_two, CharP.cast_eq_zero, GaloisField.card, NeZero.ne, Nat.card_eq_fintype_card, pow_mul, mul_comm, pow_succ, Nat.sub_add_cancel, FiniteField.pow_card

      have _ := hc
      classical
      let _ : Fintype (GaloisField 2 m) := Fintype.ofFinite (GaloisField 2 m)
      have : NeZero m := ⟨by omega⟩
      have : Fact (Nat.Prime 2) := ⟨Nat.prime_two⟩
      have h2 : (2 : GaloisField 2 m) = 0 := CharP.cast_eq_zero (GaloisField 2 m) 2
      have hcard : Nat.card (GaloisField 2 m) = 2 ^ m := GaloisField.card 2 m (NeZero.ne m)
      have hf : Fintype.card (GaloisField 2 m) = 2 ^ m := by
        rw [← Nat.card_eq_fintype_card, hcard]
      have hpow_card (y : GaloisField 2 m) : (y ^ 2) ^ (2 ^ (m - 1)) = y := by
        rw [← pow_mul, mul_comm 2, ← pow_succ, Nat.sub_add_cancel hm, ← hf, FiniteField.pow_card]
      have hpow : 2 ^ (m - 1) ≠ 0 := by positivity
  2. Choose difference witnesses $\alpha = (0, 1)$ and $\beta = (c, 0)$, and observe $\alpha \ne (0, 0)$.

    Unfolding the definition of differential uniformity, we select the specific input difference $\alpha = (0, 1)$ and output difference $\beta = (c, 0)$. The difference $\alpha$ is non-zero because its second component is $1 \ne 0$.

    lines 19–27

    uses Prod.ext_iff.mp, one_ne_zero

      unfold digit_exchange_differential_uniformity
      dsimp only
      let α : GaloisField 2 m × GaloisField 2 m := (0, 1)
      let β : GaloisField 2 m × GaloisField 2 m := (c, 0)
      have hα_ne : α ≠ (0, 0) := by
        intro h
        have : (1 : GaloisField 2 m) = 0 := Prod.ext_iff.mp h |>.2
        exact one_ne_zero this
    
  3. It suffices to show that the differential equation $\operatorname{sub}(G(\operatorname{add}(x, \alpha)), G(x)) = \beta$ has at least 2 solutions.

    Because differential uniformity is the supremum of the solution counts over all non-zero input differences $\alpha$ and all output differences $\beta$, the count at any particular pair $(\alpha, \beta)$ provides a lower bound by `Finset.le_sup`. We restate the remaining goal as showing that the solution set for our chosen $(\alpha, \beta)$ has cardinality at least 2.

    lines 28–38

    uses le_trans, Finset.le_sup

      refine le_trans ?_ (Finset.le_sup (b := α) ?_)
      · refine le_trans ?_ (Finset.le_sup (b := β) ?_)
        · let add (x y : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=
            (x.1 + y.1, x.2 + y.2 + (x.1 * y.1) ^ (2 ^ (m - 1)))
          let sub (y z : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=
            (y.1 + z.1, y.2 + z.1 + z.2 + (y.1 * z.1) ^ (2 ^ (m - 1)))
          let D (x : GaloisField 2 m) : GaloisField 2 m := x ^ 2 + x + c
          let G (x : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=
            let L := D x.1 * x.2
            (L, D L * x.1)
          change 2 ≤ (Finset.filter (fun x => sub (G (add x α)) (G x) = β) Finset.univ).card
  4. The points $x_1 = (0, 0)$ and $x_2 = (1, (c+1)^2)$ are distinct.

    We define two candidate solutions $x_1 = (0, 0)$ and $x_2 = (1, (c+1)^2)$. They are distinct because their first components are 0 and 1, respectively, and $0 \ne 1$ in the field.

    lines 40–47

    uses Prod.ext_iff.mp, zero_ne_one

          let x1 : GaloisField 2 m × GaloisField 2 m := (0, 0)
          let x2 : GaloisField 2 m × GaloisField 2 m := (1, (c + 1) ^ 2)
    
          have hx_ne : x1 ≠ x2 := by
            intro h
            have : (0 : GaloisField 2 m) = 1 := Prod.ext_iff.mp h |>.1
            exact zero_ne_one this
    
  5. $x_1 = (0, 0)$ is a solution to the differential equation.

    Plugging $x_1 = (0, 0)$ and $\alpha = (0, 1)$ into the definitions of `add`, `sub`, $D$, and $G$, direct simplification confirms that $\operatorname{sub}(G(\operatorname{add}(x_1, \alpha)), G(x_1)) = (c, 0) = \beta$.

    lines 48–50

          have hsol1 : sub (G (add x1 α)) (G x1) = β := by
            ext <;> simp [α, β, x1, add, sub, D, G]
    
  6. $x_2 = (1, (c+1)^2)$ is also a solution to the differential equation.

    We evaluate $\operatorname{sub}(G(\operatorname{add}(x_2, \alpha)), G(x_2))$ component-wise. The first component equation reduces to a polynomial identity in $c$ that holds modulo 2 (via $2 = 0$). In the second component, the power $( \cdot )^{2^{m-1}}$ acts on $((c^2(c+1))^2)$, which simplifies to $c^2(c+1)$ by the Frobenius identity $(y^2)^{2^{m-1}} = y$; the remaining expression then simplifies to 0 modulo 2.

    lines 51–62

    uses mul_zero, zero_pow, add_zero, mul_one

          have hsol2 : sub (G (add x2 α)) (G x2) = β := by
            ext
            · dsimp [α, β, x2, add, sub, D, G]
              simp only [mul_zero, zero_pow hpow, add_zero]
              linear_combination (c ^ 3 + 4 * c ^ 2 + 5 * c + 3) * h2
            · dsimp [α, β, x2, add, sub, D, G]
              simp only [mul_zero, zero_pow hpow, add_zero, mul_one]
              have hbase : (1 ^ 2 + 1 + c) * ((c + 1) ^ 2 + 1) * ((1 ^ 2 + 1 + c) * (c + 1) ^ 2) = (c ^ 2 * (c + 1)) ^ 2 := by
                linear_combination (4 + 16 * c + 27 * c ^ 2 + 25 * c ^ 3 + 13 * c ^ 4 + 3 * c ^ 5) * h2
              rw [hbase, hpow_card]
              linear_combination (14 + 43 * c + 61 * c ^ 2 + 52 * c ^ 3 + 27 * c ^ 4 + 8 * c ^ 5 + c ^ 6) * h2
    
  7. The doubleton $\{x_1, x_2\}$ is a subset of the solution set.

    Every element of $\{x_1, x_2\}$ is either $x_1$ or $x_2$. Since both have been verified as solutions, both belong to the set of solutions filtered from the universe.

    lines 63–69

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter.mpr, Finset.mem_univ

          have h_sub : {x1, x2} ⊆ Finset.filter (fun x => sub (G (add x α)) (G x) = β) Finset.univ := by
            intro x hx
            simp only [Finset.mem_insert, Finset.mem_singleton] at hx
            rcases hx with rfl | rfl
            · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hsol1⟩
            · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hsol2⟩
    
  8. The number of solutions to the differential equation is at least 2.

    Since $x_1 \ne x_2$, the set $\{x_1, x_2\}$ has cardinality 2. Because it is a subset of the solution set, subset inclusion preserves cardinality (`Finset.card_le_card`), giving $2 \le |\{x \mid \operatorname{sub}(G(\operatorname{add}(x, \alpha)), G(x)) = \beta\}|$.

    lines 70–73

    uses Finset.card_pair, le_trans, le_of_eq, Finset.card_le_card

          have h2card : ({x1, x2} : Finset (GaloisField 2 m × GaloisField 2 m)).card = 2 := by
            simp [Finset.card_pair hx_ne]
    
          exact le_trans (le_of_eq h2card.symm) (Finset.card_le_card h_sub)
  9. The witnesses $\alpha$ and $\beta$ belong to their respective domains for the supremum.

    We discharge the side conditions generated by bounding the supremum from below: $\beta$ trivially belongs to the universe `Finset.univ`, and $\alpha$ belongs to the set of non-zero pairs because $\alpha \ne (0, 0)$.

    lines 74–76

    uses Finset.mem_univ, Finset.mem_filter

        · exact Finset.mem_univ β
      · rw [Finset.mem_filter]
        exact ⟨Finset.mem_univ α, hα_ne⟩
Fintype.ofFinite
Constructs a finite type instance from a proof of finiteness.
Nat.prime_two
The number 2 is prime.
CharP.cast_eq_zero
In a ring of characteristic $p$, the image of $p$ is zero.
GaloisField.card
For prime $p$ and $n \neq 0$, the Galois field $\mathbb{F}_{p^n}$ has cardinality $p^n$.
NeZero.ne
An element with a `NeZero` instance is non-zero.
Nat.card_eq_fintype_card
The general cardinality `Nat.card` coincides with `Fintype.card` for finite types.
pow_mul
Power of a power: $a^{m \cdot n} = (a^m)^n$.
mul_comm
Multiplication is commutative: $a \cdot b = b \cdot a$.
pow_succ
Successor power: $a^{n+1} = a^n \cdot a$.
Nat.sub_add_cancel
For natural numbers with $m \le n$, $(n - m) + m = n$.
FiniteField.pow_card
In a finite field $K$, every element satisfies $a^{|K|} = a$.
Prod.ext_iff.mp
Equality of pairs implies equality of their components: $(a, b) = (c, d) \implies a = c \land b = d$.
one_ne_zero
In a non-trivial semiring with zero and one, $1 \neq 0$.
le_trans
Transitivity of inequality: $a \le b$ and $b \le c$ imply $a \le c$.
Finset.le_sup
An element of a finite set is bounded by the supremum: if $b \in s$, then $f(b) \le \sup_{x \in s} f(x)$.
zero_ne_one
In a non-trivial semiring with zero and one, $0 \neq 1$.
mul_zero
Multiplication by zero on the right gives zero: $a \cdot 0 = 0$.
zero_pow
Zero raised to a non-zero power is zero: $0^n = 0$ for $n \neq 0$.
add_zero
Adding zero on the right preserves the element: $a + 0 = a$.
mul_one
Multiplying by one on the right: $a \cdot 1 = a$.
Finset.mem_insert
Membership in an inserted set: $a \in \operatorname{insert}(b, s) \iff a = b \lor a \in s$.
Finset.mem_singleton
Membership in a singleton set: $b \in \{a\} \iff b = a$.
Finset.mem_filter.mpr
If $a \in s$ and $p(a)$ holds, then $a \in \{x \in s \mid p(x)\}$.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.card_pair
If $a \neq b$, the set $\{a, b\}$ has cardinality 2.
le_of_eq
Equality implies inequality: $a = b \implies a \le b$.
Finset.card_le_card
Subset inclusion preserves cardinality: $s \subseteq t \implies |s| \le |t|$.
Finset.mem_filter
Membership in a filtered set: $a \in \{x \in s \mid p(x)\} \iff a \in s \land p(a)$.

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

/-- Proposition 3.2 of arXiv:2611.02572: every permutation of (Z/4Z)^m has differential uniformity at least 2. -/theorem op_928_digit_exchange_differential_uniformity_ge_two    (m : ℕ) (hm : 1 ≤ m) (c : GaloisField 2 m)    (hc : Algebra.trace (ZMod 2) (GaloisField 2 m) c = 1) :    2 ≤ digit_exchange_differential_uniformity m c := by  have _ := hc  classical  let _ : Fintype (GaloisField 2 m) := Fintype.ofFinite (GaloisField 2 m)  have : NeZero m := ⟨by omega⟩  have : Fact (Nat.Prime 2) := ⟨Nat.prime_two⟩  have h2 : (2 : GaloisField 2 m) = 0 := CharP.cast_eq_zero (GaloisField 2 m) 2  have hcard : Nat.card (GaloisField 2 m) = 2 ^ m := GaloisField.card 2 m (NeZero.ne m)  have hf : Fintype.card (GaloisField 2 m) = 2 ^ m := by    rw [← Nat.card_eq_fintype_card, hcard]  have hpow_card (y : GaloisField 2 m) : (y ^ 2) ^ (2 ^ (m - 1)) = y := by    rw [← pow_mul, mul_comm 2, ← pow_succ, Nat.sub_add_cancel hm, ← hf, FiniteField.pow_card]  have hpow : 2 ^ (m - 1) ≠ 0 := by positivity  unfold digit_exchange_differential_uniformity  dsimp only  let α : GaloisField 2 m × GaloisField 2 m := (0, 1)  let β : GaloisField 2 m × GaloisField 2 m := (c, 0)  have hα_ne : α ≠ (0, 0) := by    intro h    have : (1 : GaloisField 2 m) = 0 := Prod.ext_iff.mp h |>.2    exact one_ne_zero this  refine le_trans ?_ (Finset.le_sup (b := α) ?_)  · refine le_trans ?_ (Finset.le_sup (b := β) ?_)    · let add (x y : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=        (x.1 + y.1, x.2 + y.2 + (x.1 * y.1) ^ (2 ^ (m - 1)))      let sub (y z : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=        (y.1 + z.1, y.2 + z.1 + z.2 + (y.1 * z.1) ^ (2 ^ (m - 1)))      let D (x : GaloisField 2 m) : GaloisField 2 m := x ^ 2 + x + c      let G (x : GaloisField 2 m × GaloisField 2 m) : GaloisField 2 m × GaloisField 2 m :=        let L := D x.1 * x.2        (L, D L * x.1)      change 2 ≤ (Finset.filter (fun x => sub (G (add x α)) (G x) = β) Finset.univ).card      let x1 : GaloisField 2 m × GaloisField 2 m := (0, 0)      let x2 : GaloisField 2 m × GaloisField 2 m := (1, (c + 1) ^ 2)      have hx_ne : x1 ≠ x2 := by        intro h        have : (0 : GaloisField 2 m) = 1 := Prod.ext_iff.mp h |>.1        exact zero_ne_one this      have hsol1 : sub (G (add x1 α)) (G x1) = β := by        ext <;> simp [α, β, x1, add, sub, D, G]      have hsol2 : sub (G (add x2 α)) (G x2) = β := by        ext        · dsimp [α, β, x2, add, sub, D, G]          simp only [mul_zero, zero_pow hpow, add_zero]          linear_combination (c ^ 3 + 4 * c ^ 2 + 5 * c + 3) * h2        · dsimp [α, β, x2, add, sub, D, G]          simp only [mul_zero, zero_pow hpow, add_zero, mul_one]          have hbase : (1 ^ 2 + 1 + c) * ((c + 1) ^ 2 + 1) * ((1 ^ 2 + 1 + c) * (c + 1) ^ 2) = (c ^ 2 * (c + 1)) ^ 2 := by            linear_combination (4 + 16 * c + 27 * c ^ 2 + 25 * c ^ 3 + 13 * c ^ 4 + 3 * c ^ 5) * h2          rw [hbase, hpow_card]          linear_combination (14 + 43 * c + 61 * c ^ 2 + 52 * c ^ 3 + 27 * c ^ 4 + 8 * c ^ 5 + c ^ 6) * h2      have h_sub : {x1, x2} ⊆ Finset.filter (fun x => sub (G (add x α)) (G x) = β) Finset.univ := by        intro x hx        simp only [Finset.mem_insert, Finset.mem_singleton] at hx        rcases hx with rfl | rfl        · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hsol1⟩        · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hsol2⟩      have h2card : ({x1, x2} : Finset (GaloisField 2 m × GaloisField 2 m)).card = 2 := by        simp [Finset.card_pair hx_ne]      exact le_trans (le_of_eq h2card.symm) (Finset.card_le_card h_sub)    · exact Finset.mem_univ β  · rw [Finset.mem_filter]    exact ⟨Finset.mem_univ α, hα_ne⟩
See it in the graphDiscuss this resultChallenge it