cycle_power_floor_map_induced
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
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor every natural k at least one and natural n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th…
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover…
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.
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.
classical letI : NeZero n := ⟨by omega⟩ letI : NeZero N := ⟨by omega⟩ have hN₀ : 0 < N := by omega
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.
uses
ZMod.val_cast_of_lt,nat_scaled_floor_lt,ZMod.val_lthave 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))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.
uses
ZMod.val_injective,congrArg,lt_trichotomy,nat_scaled_floor_stricthave 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
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.
uses
nat_scaled_floor_strict,simple_graph_cycle_power_adj_iff_val_lthave 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]
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.
uses
nat_scaled_floor_gap_threshold,ZMod.val_lt,Nat.add_mul,Nat.add_mul_div_lefthave 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
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.
uses
ZMod.val_lt,nat_scaled_floor_lt,nat_scaled_floor_strict,or_congrhave 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
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).
uses
lt_trichotomy,ZMod.val_injective,SimpleGraph.irrefl,SimpleGraph.adj_commrefine ⟨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.
- Because arithmetic on ℕ uses truncated subtraction (n - m = 0 when n ≤ m), algebraic identities like (u.val + n) - v.val = n - (v.val - u.val) require explicit non-negativity and ordering bounds before applying linear arithmetic.
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.
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