op_928_digit_exchange_differential_uniformity_one
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
- digit_exchange_differential_uniformityGiven an arbitrary natural number m (without any positivity or nonzeroness assumption) and an element c in GaloisField 2 m, the…
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).
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.
uses
Fintype.ofFinite,Nat.card_eq_fintype_card,GaloisField.cardclassical 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
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.
uses
CharTwo.two_eq_zero,FiniteField.pow_card,mul_eq_zero.mp,Or.inl,Or.inr,sub_eq_zero.mphave 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)
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.
uses
map_zero,absurdhave 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
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.
uses
Nat.sub_self,pow_zero,pow_one,one_mul,one_ne_zerounfold 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
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.
uses
le_antisymm,Finset.sup_leapply le_antisymm · apply Finset.sup_le rintro ⟨u, v⟩ huv apply Finset.sup_le rintro ⟨β1, β2⟩ _
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.
uses
Finset.mem_filter,Prod.mk.injEq,Finset.card_le_card_of_injOn,Finset.mem_coe.mpr,Finset.mem_univ,Finset.card_univhave 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]
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.
uses
absurd,Finset.mem_filter.mp,Prod.extrcases 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)
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.
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
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 β.
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))))
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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_filter,Finset.mem_univ,Prod.mk.injEq,le_trans,Finset.card_le_card,Finset.card_pairhave 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.
- In characteristic 2, addition and subtraction are identical, so terms like x₂ + x₂ vanish (since 2 = 0), and x² = x for every field element. The proof repeatedly relies on `linear_combination` to eliminate such terms.
- GaloisField 2 1 is Lean's representation of the finite field 𝔽₂.
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.
/-- 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