AFTD Auto-Formalizing Theoretical Domains

cycle_power_floor_map_induced

theoremverified

For natural n,N,k,K with n positive, N at least n, k*N at most K*n, and (K+1)*n at most (k+1)*N, the balanced floor map from ZMod n to ZMod N is injective and preserves and reflects adjacency from the k-th cycle power to the K-th cycle power.

Statement

theorem cycle_power_floor_map_induced
    (n N k K : ℕ) (hn : 0 < n) (hN : n ≤ N)
    (hlo : k*N ≤ K*n) (hhi : (K+1)*n ≤ (k+1)*N) :
    Function.Injective (cycle_power_floor_map n N) ∧
      ∀ u v : ZMod n, (simple_graph_cycle_power n k).Adj u v ↔
        (simple_graph_cycle_power N K).Adj (cycle_power_floor_map n N u) (cycle_power_floor_map n N v)
Source
arXiv:2610.15635, Proposition 3.2, with induced floor embedding from Lemma 3.1 and cover restriction from Lemma 2.1. This formalizes the published upper bound serving OP-205 / RT-1; no new research result is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
  • nat_scaled_floor_gap_thresholdLet n,N,k,K be natural numbers with n positive, k*N at most K*n, and (K+1)*n at most (k+1)*N. For natural i at most j, j-i is at most k if…
  • nat_scaled_floor_strictFor positive natural n and natural N at least n, the map i to floor(i*N/n) is strictly increasing on the natural numbers.
  • nat_scaled_floor_ltFor positive natural n and N, and natural i less than n, floor(i*N/n) is less than N.
  • simple_graph_cycle_power_adj_iff_val_ltFor a nonzero natural n, natural k, and vertices u,v of ZMod n with u.val less than v.val, adjacency in the k-th cycle power is equivalent…
  • cycle_power_floor_mapThe map from ZMod n to ZMod N sending a vertex u to the residue class of floor(u.val*N/n).
Used by 2

The proof, explained

The theorem proves that the floor-scaling map u ↦ ⌊u.val * N / n⌋ from ZMod n to ZMod N is an injective graph embedding (preserving and reflecting adjacency) from the k-th cycle power on n vertices into the K-th cycle power on N vertices. Injectivity follows from the strict monotonicity of integer scaling when n ≤ N. Adjacency in a cycle power is characterized as the disjunction of two linear distance conditions (forward distance and wrap-around distance); the key lemma nat_scaled_floor_gap_threshold transfers each threshold inequality faithfully under the given scaling bounds k*N ≤ K*n and (K+1)*n ≤ (k+1)*N. The full equivalence then follows for all pairs of vertices by trichotomy on their canonical representatives and graph symmetry.

  1. The moduli n and N are positive and non-zero.

    From 0 < n and n ≤ N, linear arithmetic (omega) establishes that both n and N are non-zero (registered as NeZero typeclass instances) and that 0 < N.

    lines 11–14

      classical
      letI : NeZero n := ⟨by omega⟩
      letI : NeZero N := ⟨by omega⟩
      have hN₀ : 0 < N := by omega
  2. For any u ∈ ZMod n, the representative of cycle_power_floor_map n N u in {0, ..., N - 1} is (u.val * N) / n.

    By definition, the floor map casts the integer (u.val * N) / n to ZMod N. Since u.val < n (ZMod.val_lt), nat_scaled_floor_lt ensures that this integer is strictly less than N, so taking its canonical representative in ZMod N via ZMod.val_cast_of_lt returns (u.val * N) / n.

    lines 15–16

    uses ZMod.val_cast_of_lt, nat_scaled_floor_lt, ZMod.val_lt

      have hval (u : ZMod n) : (cycle_power_floor_map n N u).val = u.val*N/n :=
        ZMod.val_cast_of_lt (nat_scaled_floor_lt n N hn hN₀ u.val (ZMod.val_lt u))
  3. The floor map cycle_power_floor_map n N is injective.

    Assume cycle_power_floor_map n N u = cycle_power_floor_map n N v. Applying congrArg ZMod.val and substituting the explicit representative formula gives (u.val * N) / n = (v.val * N) / n. By trichotomy on u.val and v.val (lt_trichotomy), strict monotonicity (nat_scaled_floor_strict) implies that u.val < v.val and v.val < u.val both contradict this equality. Therefore u.val = v.val, which implies u = v by ZMod.val_injective.

    lines 17–27

    uses ZMod.val_injective, congrArg, lt_trichotomy, nat_scaled_floor_strict

      have hinj : Function.Injective (cycle_power_floor_map n N) := by
        intro u v he
        apply ZMod.val_injective
        have heval := congrArg ZMod.val he
        rw [hval u, hval v] at heval
        rcases lt_trichotomy u.val v.val with h | h | h
        · have := nat_scaled_floor_strict n N hn hN u.val v.val h
          omega
        · exact h
        · have := nat_scaled_floor_strict n N hn hN v.val u.val h
          omega
  4. When u.val < v.val, the mapped representatives satisfy (f(u)).val < (f(v)).val, and adjacency in both cycle powers reduces to disjunctions of two distance bounds.

    Because u.val < v.val, strict monotonicity (nat_scaled_floor_strict) ensures that (cycle_power_floor_map n N u).val < (cycle_power_floor_map n N v).val. Using simple_graph_cycle_power_adj_iff_val_lt and the value formula on both sides, adjacency in the k-th cycle power on n vertices reduces to (v.val - u.val ≤ k ∨ n - (v.val - u.val) ≤ k), and adjacency in the K-th cycle power on N vertices reduces to the corresponding disjunction on the scaled values with threshold K.

    lines 28–35

    uses nat_scaled_floor_strict, simple_graph_cycle_power_adj_iff_val_lt

      have hlt (u v : ZMod n) (huv : u.val < v.val) :
          (simple_graph_cycle_power n k).Adj u v ↔
            (simple_graph_cycle_power N K).Adj (cycle_power_floor_map n N u) (cycle_power_floor_map n N v) := by
        have ht : (cycle_power_floor_map n N u).val < (cycle_power_floor_map n N v).val := by
          rw [hval u, hval v]
          exact nat_scaled_floor_strict n N hn hN u.val v.val huv
        rw [simple_graph_cycle_power_adj_iff_val_lt n k u v huv,
          simple_graph_cycle_power_adj_iff_val_lt N K _ _ ht, hval u, hval v]
  5. The direct gap threshold transfers between the cycles, and the wrapped gap threshold transfers using the period shift ((u.val + n) * N) / n = (u.val * N) / n + N.

    Applying nat_scaled_floor_gap_threshold to u.val ≤ v.val equates the direct forward gap conditions v.val - u.val ≤ k and (v.val * N) / n - (u.val * N) / n ≤ K. Applying it to v.val ≤ u.val + n equates the wrapped gap (u.val + n) - v.val ≤ k with the scaled gap ((u.val + n) * N) / n - (v.val * N) / n ≤ K. Distributing the multiplication and division (Nat.add_mul and Nat.add_mul_div_left) simplifies ((u.val + n) * N) / n to (u.val * N) / n + N.

    lines 36–42

    uses nat_scaled_floor_gap_threshold, ZMod.val_lt, Nat.add_mul, Nat.add_mul_div_left

        have hfirst := nat_scaled_floor_gap_threshold n N k K hn hlo hhi u.val v.val huv.le
        have hwrap := nat_scaled_floor_gap_threshold n N k K hn hlo hhi v.val (u.val+n)
          (by have := ZMod.val_lt v; omega)
        have hperiod : (u.val+n)*N/n = u.val*N/n+N := by
          rw [Nat.add_mul]
          rw [Nat.add_mul_div_left _ _ hn]
        rw [hperiod] at hwrap
  6. When u.val < v.val, u and v are adjacent in the k-th cycle power if and only if their images are adjacent in the K-th cycle power.

    Linear arithmetic rewrites (u.val + n) - v.val as n - (v.val - u.val) and the scaled wrapped difference as N - ((v.val * N) / n - (u.val * N) / n), justified by bounds from nat_scaled_floor_lt and nat_scaled_floor_strict. Substituting these into the wrapped gap equivalence and combining with the forward gap equivalence via or_congr completes the equivalence for u.val < v.val.

    lines 43–49

    uses ZMod.val_lt, nat_scaled_floor_lt, nat_scaled_floor_strict, or_congr

        have he₀ : u.val+n-v.val = n-(v.val-u.val) := by have := ZMod.val_lt v; omega
        have he₁ : u.val*N/n+N-v.val*N/n = N-(v.val*N/n-u.val*N/n) := by
          have h₀ := nat_scaled_floor_lt n N hn hN₀ v.val (ZMod.val_lt v)
          have h₁ := nat_scaled_floor_strict n N hn hN u.val v.val huv
          omega
        rw [he₀, he₁] at hwrap
        exact or_congr hfirst hwrap
  7. The floor map is injective and preserves and reflects adjacency for all pairs of vertices.

    Injectivity was already shown. For any u and v, trichotomy (lt_trichotomy) gives three cases: if u.val < v.val, the result follows from the ordered case hlt; if u.val = v.val, then u = v by ZMod.val_injective, and neither side is adjacent by irreflexivity of simple graphs (SimpleGraph.irrefl); if v.val < u.val, the equivalence follows from hlt v u by symmetry of adjacency (SimpleGraph.adj_comm).

    lines 50–58

    uses lt_trichotomy, ZMod.val_injective, SimpleGraph.irrefl, SimpleGraph.adj_comm

      refine ⟨hinj, ?_⟩
      intro u v
      rcases lt_trichotomy u.val v.val with h | h | h
      · exact hlt u v h
      · have he : u = v := ZMod.val_injective n h
        subst v
        simp only [SimpleGraph.irrefl]
      · have he := hlt v u h
        simpa only [SimpleGraph.adj_comm] using he
Nat.add_mul
Right-distributivity of multiplication over addition for natural numbers: (n + m) * k = n * k + m * k.
Nat.add_mul_div_left
For y > 0, integer division satisfies (x + y * z) / y = x / y + z.
SimpleGraph.adj_comm
Adjacency in a simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u.
SimpleGraph.irrefl
Simple graphs contain no self-loops: no vertex is adjacent to itself.
ZMod.val_injective
The canonical representative map val from ZMod n to ℕ is injective.
ZMod.val_cast_of_lt
If a natural number a < n, then the representative in {0, ..., n - 1} of its image in ZMod n is a itself.
ZMod.val_lt
For non-zero n, the canonical representative of any element in ZMod n is strictly less than n.
congrArg
Equal arguments to a function yield equal values: if a₁ = a₂, then f a₁ = f a₂.
lt_trichotomy
Any two elements a, b in a linear order satisfy exactly one of a < b, a = b, or b < a.
nat_scaled_floor_gap_threshold
Under the ratio bounds k*N ≤ K*n and (K+1)*n ≤ (k+1)*N with 0 < n, two natural numbers with i ≤ j satisfy j - i ≤ k if and only if their scaled floors satisfy (j*N/n) - (i*N/n) ≤ K.
nat_scaled_floor_lt
If 0 < n and 0 < N, the scaled floor (i*N/n) of any index i < n is strictly less than N.
nat_scaled_floor_strict
When 0 < n ≤ N, the scaled floor map i ↦ i*N/n is strictly monotonically increasing on natural numbers.
or_congr
If two pairs of propositions are equivalent, their disjunctions are equivalent: (a ↔ c) → (b ↔ d) → (a ∨ b ↔ c ∨ d).
simple_graph_cycle_power_adj_iff_val_lt
For vertices u, v in ZMod n with u.val < v.val, adjacency in the k-th cycle power is equivalent to either their forward distance v.val - u.val ≤ k or their wrapped distance n - (v.val - u.val) ≤ k.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_floor_map_induced    (n N k K : ℕ) (hn : 0 < n) (hN : n ≤ N)    (hlo : k*N ≤ K*n) (hhi : (K+1)*n ≤ (k+1)*N) :    Function.Injective (cycle_power_floor_map n N) ∧      ∀ u v : ZMod n, (simple_graph_cycle_power n k).Adj u v ↔        (simple_graph_cycle_power N K).Adj (cycle_power_floor_map n N u) (cycle_power_floor_map n N v) := by  classical  letI : NeZero n := ⟨by omega⟩  letI : NeZero N := ⟨by omega⟩  have hN₀ : 0 < N := by omega  have hval (u : ZMod n) : (cycle_power_floor_map n N u).val = u.val*N/n :=    ZMod.val_cast_of_lt (nat_scaled_floor_lt n N hn hN₀ u.val (ZMod.val_lt u))  have hinj : Function.Injective (cycle_power_floor_map n N) := by    intro u v he    apply ZMod.val_injective    have heval := congrArg ZMod.val he    rw [hval u, hval v] at heval    rcases lt_trichotomy u.val v.val with h | h | h    · have := nat_scaled_floor_strict n N hn hN u.val v.val h      omega    · exact h    · have := nat_scaled_floor_strict n N hn hN v.val u.val h      omega  have hlt (u v : ZMod n) (huv : u.val < v.val) :      (simple_graph_cycle_power n k).Adj u v ↔        (simple_graph_cycle_power N K).Adj (cycle_power_floor_map n N u) (cycle_power_floor_map n N v) := by    have ht : (cycle_power_floor_map n N u).val < (cycle_power_floor_map n N v).val := by      rw [hval u, hval v]      exact nat_scaled_floor_strict n N hn hN u.val v.val huv    rw [simple_graph_cycle_power_adj_iff_val_lt n k u v huv,      simple_graph_cycle_power_adj_iff_val_lt N K _ _ ht, hval u, hval v]    have hfirst := nat_scaled_floor_gap_threshold n N k K hn hlo hhi u.val v.val huv.le    have hwrap := nat_scaled_floor_gap_threshold n N k K hn hlo hhi v.val (u.val+n)      (by have := ZMod.val_lt v; omega)    have hperiod : (u.val+n)*N/n = u.val*N/n+N := by      rw [Nat.add_mul]      rw [Nat.add_mul_div_left _ _ hn]    rw [hperiod] at hwrap    have he₀ : u.val+n-v.val = n-(v.val-u.val) := by have := ZMod.val_lt v; omega    have he₁ : u.val*N/n+N-v.val*N/n = N-(v.val*N/n-u.val*N/n) := by      have h₀ := nat_scaled_floor_lt n N hn hN₀ v.val (ZMod.val_lt v)      have h₁ := nat_scaled_floor_strict n N hn hN u.val v.val huv      omega    rw [he₀, he₁] at hwrap    exact or_congr hfirst hwrap  refine ⟨hinj, ?_⟩  intro u v  rcases lt_trichotomy u.val v.val with h | h | h  · exact hlt u v h  · have he : u = v := ZMod.val_injective n h    subst v    simp only [SimpleGraph.irrefl]  · have he := hlt v u h    simpa only [SimpleGraph.adj_comm] using he
See it in the graphDiscuss this resultChallenge it