AFTD Auto-Formalizing Theoretical Domains

op_928_digit_exchange_differential_uniformity_one

theoremverifiedformalization

For m = 1 and any element c in GaloisField 2 1 with absolute trace Algebra.trace (ZMod 2) (GaloisField 2 1) c = 1, the differential uniformity digit_exchange_differential_uniformity 1 c is equal to 2.

Statement

theorem op_928_digit_exchange_differential_uniformity_one
    (c : GaloisField 2 1)
    (hc : Algebra.trace (ZMod 2) (GaloisField 2 1) c = 1) :
    digit_exchange_differential_uniformity 1 c = 2
Formalizes
arXiv:2611.02572, Table 1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

Let $c \in \operatorname{GaloisField}(2, 1)$ such that the trace of $c$ from $\operatorname{GaloisField}(2, 1)$ to $\mathbb{Z}/2\mathbb{Z}$ is $1$ (i.e., $\operatorname{Tr}_{\mathbb{Z}/2\mathbb{Z}}^{\operatorname{GaloisField}(2, 1)}(c) = 1$). Then the digit-exchange differential uniformity digit_exchange_differential_uniformity 1 c is equal to $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 construction for m = 1 is the maximum size of the preimage fibers of the difference map over non-zero input differences α and targets β in (𝔽₂)^2. In 𝔽₂, the trace condition forces c = 1, which collapses the polynomial D(t) = t^2 + t + c to the constant 1. The upper bound ≤ 2 is proved by showing that each fiber injects into 𝔽₂: via projection to the first coordinate when the first component of α is 0, and via projection to the second coordinate when it is 1. The lower bound ≥ 2 is established by observing that for difference α = (0, 1) and target β = (1, 0), the fiber contains the two distinct points (0, 0) and (1, 0).

  1. The field GaloisField 2 1 has exactly 2 elements.

    The cardinality of GaloisField p n is p^n, which for p = 2 and n = 1 evaluates to 2^1 = 2.

    lines 6–10

    uses Fintype.ofFinite, Nat.card_eq_fintype_card, GaloisField.card

      classical
      let _ : Fintype (GaloisField 2 1) := Fintype.ofFinite _
      have hcard : Fintype.card (GaloisField 2 1) = 2 := by
        rw [← Nat.card_eq_fintype_card, GaloisField.card 2 1 (by omega)]
        norm_num
  2. In GaloisField 2 1, 2 = 0, every element satisfies t^2 = t, and every element is either 0 or 1.

    The field has characteristic 2, so 2 = 0. By Fermat's Little Theorem for finite fields, t^|K| = t, giving t^2 = t. Factoring t(t - 1) = t^2 - t = 0 in a field implies that every element is either 0 or 1.

    lines 11–19

    uses CharTwo.two_eq_zero, FiniteField.pow_card, mul_eq_zero.mp, Or.inl, Or.inr, sub_eq_zero.mp

      have h2 : (2 : GaloisField 2 1) = 0 := CharTwo.two_eq_zero
      have hsq : ∀ t : GaloisField 2 1, t ^ 2 = t := by
        intro t; have := FiniteField.pow_card t; rwa [hcard] at this
      have h01 : ∀ t : GaloisField 2 1, t = 0 ∨ t = 1 := by
        intro t
        have : t * (t - 1) = 0 := by linear_combination hsq t
        rcases mul_eq_zero.mp this with h | h
        · exact Or.inl h
        · exact Or.inr (sub_eq_zero.mp h)
  3. The parameter c must equal 1, and the polynomial D(t) = t^2 + t + 1 is identically 1.

    Since c ∈ {0, 1} and the trace is linear with Tr(0) = 0 ≠ 1, the condition Tr(c) = 1 forces c = 1. With c = 1, D(t) = t^2 + t + 1 = t + t + 1 = 2t + 1 = 1 for all t.

    lines 20–26

    uses map_zero, absurd

      have hc1 : c = 1 := by
        rcases h01 c with h | h
        · rw [h, map_zero] at hc; exact absurd hc (by decide)
        · exact h
      subst hc1
      have hD : ∀ t : GaloisField 2 1, t ^ 2 + t + 1 = 1 := by
        intro t; rw [hsq]; linear_combination t * h2
  4. The differential uniformity formula simplifies to the supremum of the preimage sizes of the difference map, and 1 ≠ 0 holds.

    Unfolding the definition of differential uniformity for m = 1, the exponents 2^(m - 1) = 2^0 = 1 become 1, and D simplifies to 1. The uniformity is thus the supremum over all non-zero α and all β of the number of solutions x to the difference equation. Also, 1 ≠ 0 in any nontrivial field.

    lines 27–29

    uses Nat.sub_self, pow_zero, pow_one, one_mul, one_ne_zero

      unfold digit_exchange_differential_uniformity
      simp only [Nat.sub_self, pow_zero, pow_one, hD, one_mul]
      have h10 : (1 : GaloisField 2 1) ≠ 0 := one_ne_zero
  5. By antisymmetry, it suffices to prove the upper bound ≤ 2 and lower bound ≥ 2; for the upper bound, it suffices to bound the fiber size by 2 for each non-zero difference α = (u, v) and target β = (β₁, β₂).

    Antisymmetry splits the equality into two inequalities. The supremum over all non-zero α and all β is at most 2 provided every individual fiber has at most 2 elements.

    lines 30–34

    uses le_antisymm, Finset.sup_le

      apply le_antisymm
      · apply Finset.sup_le
        rintro ⟨u, v⟩ huv
        apply Finset.sup_le
        rintro ⟨β1, β2⟩ _
  6. Any element of the fiber satisfies the two coordinate equations, and any injection from the fiber into GaloisField 2 1 bounds the fiber cardinality by 2.

    Elements in the fiber satisfy the system of two coordinate equations matching (β₁, β₂). Since the target field has cardinality 2, exhibiting an injective function from the fiber to the field proves that the fiber has size at most 2.

    lines 35–50

    uses Finset.mem_filter, Prod.mk.injEq, Finset.card_le_card_of_injOn, Finset.mem_coe.mpr, Finset.mem_univ, Finset.card_univ

        have hS : ∀ x ∈ Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>
            (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2)),
            x.2 + v + x.1 * u + x.2 = β1 ∧ x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2 = β2 := by
          intro x hx
          rw [Finset.mem_filter, Prod.mk.injEq] at hx
          exact hx.2
        have hle : ∀ (f : GaloisField 2 1 × GaloisField 2 1 → GaloisField 2 1),
            Set.InjOn f ↑(Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>
            (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2))) →
            (Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>
            (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2))).card
              ≤ 2 := by
          intro f hf
          calc _ ≤ (Finset.univ : Finset (GaloisField 2 1)).card :=
                Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_coe.mpr (Finset.mem_univ _)) hf
            _ = 2 := by rw [Finset.card_univ, hcard]
  7. When u = 0, v must equal 1, and the projection onto the first coordinate is injective on the fiber, showing the fiber has at most 2 elements.

    Since (u, v) ≠ (0, 0), u = 0 forces v = 1. In characteristic 2, the second coordinate equation simplifies to x₂ = β₂. Because x₂ is uniquely determined by β₂, any two solutions that agree on their first coordinate x₁ must be completely identical.

    lines 51–63

    uses absurd, Finset.mem_filter.mp, Prod.ext

        rcases h01 u with rfl | rfl
        · have hv : v = 1 := by
            rcases h01 v with rfl | h
            · exact absurd rfl (Finset.mem_filter.mp huv).2
            · exact h
          subst hv
          apply hle (fun x => x.1)
          intro x hx y hy hxy
          have ex := (hS x hx).2
          have ey := (hS y hy).2
          have e2x : x.2 = β2 := by linear_combination ex + (-(x.1 + x.2)) * h2 + (-1) * hsq x.2
          have e2y : y.2 = β2 := by linear_combination ey + (-(y.1 + y.2)) * h2 + (-1) * hsq y.2
          exact Prod.ext hxy (e2x.trans e2y.symm)
  8. When u = 1, projection onto the second coordinate is injective on the fiber, showing the fiber has at most 2 elements.

    When u = 1, the first coordinate equation simplifies to x₁ = β₁ - v. Thus x₁ is uniquely determined, so any two solutions that share their second coordinate x₂ are identical. This completes the upper bound ≤ 2.

    lines 64–70

    uses Prod.ext

        · apply hle (fun x => x.2)
          intro x hx y hy hxy
          have ex := (hS x hx).1
          have ey := (hS y hy).1
          have e1x : x.1 = β1 - v := by linear_combination ex + (-x.2) * h2
          have e1y : y.1 = β1 - v := by linear_combination ey + (-y.2) * h2
          exact Prod.ext (e1x.trans e1y.symm) hxy
  9. To establish the lower bound ≥ 2, it suffices to exhibit a non-zero α = (0, 1) and target β = (1, 0) whose fiber has at least 2 elements.

    The difference α = (0, 1) is non-zero because 1 ≠ 0. The supremum over all non-zero α and all β is bounded below by the cardinality of the fiber at this specific choice of α and β.

    lines 71–77

    uses Finset.mem_filter, Finset.mem_univ, Prod.mk.injEq, le_trans, Finset.le_sup

      · have hα : ((0 : GaloisField 2 1), (1 : GaloisField 2 1)) ∈
            Finset.univ.filter (fun α : GaloisField 2 1 × GaloisField 2 1 => α ≠ (0, 0)) := by
          rw [Finset.mem_filter]
          refine ⟨Finset.mem_univ _, ?_⟩
          intro h; rw [Prod.mk.injEq] at h; exact h10 h.2
        refine le_trans ?_ (Finset.le_sup hα)
        refine le_trans ?_ (Finset.le_sup (Finset.mem_univ ((1 : GaloisField 2 1), (0 : GaloisField 2 1))))
  10. The fiber for α = (0, 1) and β = (1, 0) contains both (0, 0) and (1, 0), which are distinct, proving the fiber has cardinality at least 2.

    Evaluating the difference map at (0, 0) and (1, 0) shows both evaluate to (1, 0). Because 0 ≠ 1, these two points are distinct, so the pair {(0, 0), (1, 0)} has cardinality 2. Hence the fiber contains at least 2 elements, completing the proof.

    lines 78–95

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter, Finset.mem_univ, Prod.mk.injEq, le_trans, Finset.card_le_card, Finset.card_pair

        have hsub : ({(0, 0), (1, 0)} : Finset (GaloisField 2 1 × GaloisField 2 1)) ⊆
            Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>
            (x.2 + (0, 1).2 + x.1 * (0, 1).1 + x.2,
              x.1 + (0, 1).1 + x.2 + x.1 + (x.2 + (0, 1).2 + x.1 * (0, 1).1) * x.2) =
              ((1 : GaloisField 2 1), (0 : GaloisField 2 1))) := by
          intro x hx
          rw [Finset.mem_insert, Finset.mem_singleton] at hx
          rw [Finset.mem_filter]
          refine ⟨Finset.mem_univ _, ?_⟩
          rcases hx with rfl | rfl
          · simp
          · simp only [Prod.mk.injEq]
            constructor
            · ring
            · linear_combination h2
        refine le_trans ?_ (Finset.card_le_card hsub)
        rw [Finset.card_pair]
        intro h; rw [Prod.mk.injEq] at h; exact h10 h.1.symm
Fintype.ofFinite
A finite type can be given a Fintype instance.
Nat.card_eq_fintype_card
The cardinality of a type measured by Nat.card equals its Fintype.card.
GaloisField.card
The Galois field of characteristic p and degree n has p^n elements (for n ≠ 0).
CharTwo.two_eq_zero
In characteristic 2, 2 = 0.
FiniteField.pow_card
In a finite field K, every element satisfies a^|K| = a.
mul_eq_zero.mp
If a product a * b = 0, then a = 0 or b = 0.
Or.inl
Introduces a disjunction P ∨ Q from a proof of P.
Or.inr
Introduces a disjunction P ∨ Q from a proof of Q.
sub_eq_zero.mp
If a - b = 0, then a = b.
map_zero
A zero-preserving map sends 0 to 0.
absurd
From a contradiction (a proposition and its negation), anything follows.
Nat.sub_self
For any natural number n, n - n = 0.
pow_zero
Any element raised to the power 0 equals 1.
pow_one
Any element raised to the power 1 equals itself.
one_mul
Multiplying by 1 on the left is the identity.
one_ne_zero
In a nontrivial ring, 1 ≠ 0.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
Finset.sup_le
The supremum of a finite set is ≤ a if every element in the set maps to a value ≤ a.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Prod.mk.injEq
Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Finset.card_le_card_of_injOn
If a map f from finset s to finset t is injective on s, then |s| ≤ |t|.
Finset.mem_coe.mpr
An element of a finset belongs to its coercion as a set.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
Finset.card_univ
The cardinality of Finset.univ equals Fintype.card.
Finset.mem_filter.mp
If an element belongs to a filtered finset, it satisfies the filter predicate.
Prod.ext
Two pairs are equal if their corresponding components are equal.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.le_sup
The supremum of a finset is at least the value at any element in the finset.
Finset.mem_insert
An element is in insert b s if and only if it equals b or is in s.
Finset.mem_singleton
An element is in the singleton {a} if and only if it equals a.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.card_pair
If a ≠ b, then the pair {a, b} has cardinality 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

/-- Base case m = 1 (Table 1 of arXiv:2611.02572): differential uniformity of G_c is equal to 2. -/theorem op_928_digit_exchange_differential_uniformity_one    (c : GaloisField 2 1)    (hc : Algebra.trace (ZMod 2) (GaloisField 2 1) c = 1) :    digit_exchange_differential_uniformity 1 c = 2 := by  classical  let _ : Fintype (GaloisField 2 1) := Fintype.ofFinite _  have hcard : Fintype.card (GaloisField 2 1) = 2 := by    rw [← Nat.card_eq_fintype_card, GaloisField.card 2 1 (by omega)]    norm_num  have h2 : (2 : GaloisField 2 1) = 0 := CharTwo.two_eq_zero  have hsq : ∀ t : GaloisField 2 1, t ^ 2 = t := by    intro t; have := FiniteField.pow_card t; rwa [hcard] at this  have h01 : ∀ t : GaloisField 2 1, t = 0 ∨ t = 1 := by    intro t    have : t * (t - 1) = 0 := by linear_combination hsq t    rcases mul_eq_zero.mp this with h | h    · exact Or.inl h    · exact Or.inr (sub_eq_zero.mp h)  have hc1 : c = 1 := by    rcases h01 c with h | h    · rw [h, map_zero] at hc; exact absurd hc (by decide)    · exact h  subst hc1  have hD : ∀ t : GaloisField 2 1, t ^ 2 + t + 1 = 1 := by    intro t; rw [hsq]; linear_combination t * h2  unfold digit_exchange_differential_uniformity  simp only [Nat.sub_self, pow_zero, pow_one, hD, one_mul]  have h10 : (1 : GaloisField 2 1) ≠ 0 := one_ne_zero  apply le_antisymm  · apply Finset.sup_le    rintro ⟨u, v⟩ huv    apply Finset.sup_le    rintro ⟨β1, β2⟩ _    have hS : ∀ x ∈ Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>        (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2)),        x.2 + v + x.1 * u + x.2 = β1 ∧ x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2 = β2 := by      intro x hx      rw [Finset.mem_filter, Prod.mk.injEq] at hx      exact hx.2    have hle : ∀ (f : GaloisField 2 1 × GaloisField 2 1 → GaloisField 2 1),        Set.InjOn f ↑(Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>        (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2))) →        (Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>        (x.2 + v + x.1 * u + x.2, x.1 + u + x.2 + x.1 + (x.2 + v + x.1 * u) * x.2) = (β1, β2))).card          ≤ 2 := by      intro f hf      calc _ ≤ (Finset.univ : Finset (GaloisField 2 1)).card :=            Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_coe.mpr (Finset.mem_univ _)) hf        _ = 2 := by rw [Finset.card_univ, hcard]    rcases h01 u with rfl | rfl    · have hv : v = 1 := by        rcases h01 v with rfl | h        · exact absurd rfl (Finset.mem_filter.mp huv).2        · exact h      subst hv      apply hle (fun x => x.1)      intro x hx y hy hxy      have ex := (hS x hx).2      have ey := (hS y hy).2      have e2x : x.2 = β2 := by linear_combination ex + (-(x.1 + x.2)) * h2 + (-1) * hsq x.2      have e2y : y.2 = β2 := by linear_combination ey + (-(y.1 + y.2)) * h2 + (-1) * hsq y.2      exact Prod.ext hxy (e2x.trans e2y.symm)    · apply hle (fun x => x.2)      intro x hx y hy hxy      have ex := (hS x hx).1      have ey := (hS y hy).1      have e1x : x.1 = β1 - v := by linear_combination ex + (-x.2) * h2      have e1y : y.1 = β1 - v := by linear_combination ey + (-y.2) * h2      exact Prod.ext (e1x.trans e1y.symm) hxy  · have hα : ((0 : GaloisField 2 1), (1 : GaloisField 2 1)) ∈        Finset.univ.filter (fun α : GaloisField 2 1 × GaloisField 2 1 => α ≠ (0, 0)) := by      rw [Finset.mem_filter]      refine ⟨Finset.mem_univ _, ?_⟩      intro h; rw [Prod.mk.injEq] at h; exact h10 h.2    refine le_trans ?_ (Finset.le_sup hα)    refine le_trans ?_ (Finset.le_sup (Finset.mem_univ ((1 : GaloisField 2 1), (0 : GaloisField 2 1))))    have hsub : ({(0, 0), (1, 0)} : Finset (GaloisField 2 1 × GaloisField 2 1)) ⊆        Finset.univ.filter (fun x : GaloisField 2 1 × GaloisField 2 1 =>        (x.2 + (0, 1).2 + x.1 * (0, 1).1 + x.2,          x.1 + (0, 1).1 + x.2 + x.1 + (x.2 + (0, 1).2 + x.1 * (0, 1).1) * x.2) =          ((1 : GaloisField 2 1), (0 : GaloisField 2 1))) := by      intro x hx      rw [Finset.mem_insert, Finset.mem_singleton] at hx      rw [Finset.mem_filter]      refine ⟨Finset.mem_univ _, ?_⟩      rcases hx with rfl | rfl      · simp      · simp only [Prod.mk.injEq]        constructor        · ring        · linear_combination h2    refine le_trans ?_ (Finset.card_le_card hsub)    rw [Finset.card_pair]    intro h; rw [Prod.mk.injEq] at h; exact h10 h.1.symm
See it in the graphDiscuss this resultChallenge it