as_dt_path_intersection_le_two
For any natural number n and any coordinate functions a1 and a2 satisfying IsASPath, the intersection of asTrace n a1 and dtTrace n a2 has cardinality at most two.
Statement
theorem as_dt_path_intersection_le_two (n : ℕ) (a1 a2 : ℤ → ℤ) (h1 : IsASPath a1) (h2 : IsASPath a2) : (asTrace n a1 ∩ dtTrace n a2).card ≤ 2- Formalizes
- arXiv:2611.12329 Piercing a Chessboard with Restricted Slopes, Section 1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- IsASPathAn ascending shallow (AS) path coordinate function a : ℤ → ℤ satisfies 0 ≤ a(t+1) - a(t) ≤ 1 and a(t+2) ≥ a(t) + 1 for all t ∈ ℤ.
- asTraceThe trace of an ascending shallow path with coordinate function a : ℤ → ℤ on the n × n chessboard is the finite set of cells in chessboard…
- dtTraceThe trace of a descending steep (DT) path with underlying AS coordinate function a : ℤ → ℤ on the n × n chessboard is the image of asTrace…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - rotCWThe clockwise quarter-turn rotation on pairs of natural numbers (ℕ × ℕ) parameterized by n : ℕ maps (x, y) to (y, n - 1 - x).
- chessboardFor any natural number n, the chessboard of size n is the finite set of pairs of natural numbers (Finset (ℕ × ℕ)) given by the Cartesian…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For every natural number $n$ and every pair of functions $a_1, a_2 : \mathbb{Z} \to \mathbb{Z}$, if both $a_1$ and $a_2$ satisfy IsASPath, then the intersection of asTrace n a_1 and dtTrace n a_2 contains at most 2 elements.
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 proof proceeds by contradiction, assuming that the intersection of an AS path trace and a DT path trace contains at least three distinct points. Points on an AS trace are totally ordered such that both coordinates vary in the same direction, whereas points on a DT trace are anti-correlated so that the coordinates vary in opposite directions; hence, any two intersection points must share either their row or their column. By a geometric parity lemma, three points pairwise sharing a coordinate must all lie on the same row or all lie on the same column, but an AS trace cannot contain three points in the same column and a DT trace cannot contain three points in the same row, yielding an immediate contradiction.
The coordinate function a of an AS path is monotonically non-decreasing.
We express the difference as t2 = t1 + k for k ∈ ℕ and proceed by induction on k. The base case k = 0 is trivial. For the successor step, the first condition of IsASPath asserts that every single-step increment a(t + 1) - a(t) is non-negative, and combining this with the inductive hypothesis shows a(t1) ≤ a(t1 + k + 1).
obtain ⟨k, rfl⟩ : ∃ k : ℕ, t2 = t1 + k := ⟨(t2 - t1).toNat, by omega⟩ clear hle induction' k with k ih · simp · have hstep : 0 ≤ a (t1 + (k : ℤ) + 1) - a (t1 + (k : ℤ)) := (h (t1 + k)).1 have h1 : a (t1 + (k : ℤ)) ≤ a (t1 + (k + 1 : ℕ)) := by have : (t1 + (k + 1 : ℕ) : ℤ) = t1 + (k : ℤ) + 1 := by push_cast; ring rw [this] linarith have h2 : a t1 ≤ a (t1 + (k : ℤ)) := ih linarith
The function t ↦ t - a(t) is monotonically non-decreasing for any AS path a.
Writing t2 = t1 + k with k ∈ ℕ, we induct on k. The base case k = 0 is immediate. For the inductive step, the second condition of IsASPath states that a(t + 1) - a(t) ≤ 1, which rearranges to t - a(t) ≤ (t + 1) - a(t + 1). Chaining this with the induction hypothesis yields t1 - a(t1) ≤ t2 - a(t2).
obtain ⟨k, rfl⟩ : ∃ k : ℕ, t2 = t1 + k := ⟨(t2 - t1).toNat, by omega⟩ clear hle induction' k with k ih · simp · have hstep : a (t1 + (k : ℤ) + 1) - a (t1 + (k : ℤ)) ≤ 1 := (h (t1 + k)).2.1 have h1 : t1 + (k : ℤ) - a (t1 + (k : ℤ)) ≤ t1 + (k + 1 : ℕ) - a (t1 + (k + 1 : ℕ)) := by have : (t1 + (k + 1 : ℕ) : ℤ) = t1 + (k : ℤ) + 1 := by push_cast; ring rw [this] linarith linarith
An interval of length at least two increases a by at least one: if t1 + 2 ≤ t2, then a(t1) + 1 ≤ a(t2).
The third property in the definition of IsASPath directly gives a(t1) + 1 ≤ a(t1 + 2). Since t1 + 2 ≤ t2, the monotonicity of a implies a(t1 + 2) ≤ a(t2), and transitivity completes the claim.
uses
as_dt_path_intersection_le_two_isASPath_monohave hstep : a t1 + 1 ≤ a (t1 + 2) := (h t1).2.2 have hmono : a (t1 + 2) ≤ a t2 := as_dt_path_intersection_le_two_isASPath_mono h h2 linarith
Points on the trace of an AS path are totally ordered under the product ordering: either both coordinates increase (or stay equal), or both decrease.
A point p = (x, y) on the AS trace satisfies x = a(x + y) and y = (x + y) - a(x + y). Comparing the diagonal sums p.1 + p.2 and q.1 + q.2, if p.1 + p.2 ≤ q.1 + q.2, then monotonicity of a gives p.1 ≤ q.1 and monotonicity of t ↦ t - a(t) gives p.2 ≤ q.2. If instead q.1 + q.2 ≤ p.1 + p.2, the reverse inequalities hold symmetrically.
uses
as_dt_path_intersection_le_two_isASPath_mono,as_dt_path_intersection_le_two_isASPath_sub_mono,Finset.mem_filtersimp only [asTrace, Finset.mem_filter] at hp hq have ap := hp.2; have aq := hq.2 have h_cases : (↑p.1 + ↑p.2 : ℤ) ≤ ↑q.1 + ↑q.2 ∨ (↑q.1 + ↑q.2 : ℤ) ≤ ↑p.1 + ↑p.2 := by omega rcases h_cases with hle | hle · left have h1 := as_dt_path_intersection_le_two_isASPath_mono ha hle have h2 := as_dt_path_intersection_le_two_isASPath_sub_mono ha hle constructor <;> omega · right have h1 := as_dt_path_intersection_le_two_isASPath_mono ha hle have h2 := as_dt_path_intersection_le_two_isASPath_sub_mono ha hle constructor <;> omega
Points on the trace of a DT path satisfy an anti-correlated coordinate ordering: if the first coordinate increases, the second decreases or stays equal.
Every point in the DT trace is the clockwise 90-degree rotation (y, n - 1 - x) of a point (x, y) in the AS trace. Applying the product ordering of the underlying AS points, an increase in the rotated first coordinate (the original y) corresponds to a decrease (or equality) in the rotated second coordinate n - 1 - x, since x also increases or stays equal.
uses
as_dt_path_intersection_le_two_asTrace_order,Finset.mem_image,Finset.mem_filter.mp,Finset.mem_product,Finset.mem_rangesimp only [dtTrace, Finset.mem_image] at hp hq obtain ⟨p0, hp0, rfl⟩ := hp obtain ⟨q0, hq0, rfl⟩ := hq have hp0_cb : p0 ∈ chessboard n := (Finset.mem_filter.mp hp0).1 have hq0_cb : q0 ∈ chessboard n := (Finset.mem_filter.mp hq0).1 simp only [chessboard, Finset.mem_product, Finset.mem_range] at hp0_cb hq0_cb rcases p0 with ⟨px, py⟩ rcases q0 with ⟨qx, qy⟩ simp only [rotCW] have h := as_dt_path_intersection_le_two_asTrace_order ha (px, py) (qx, qy) hp0 hq0 rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · left; constructor <;> omega · right; constructor <;> omega
If three pairwise distinct points pairwise share a coordinate, then either all three share their first coordinate or all three share their second coordinate.
By case analysis on the three coordinate-equality hypotheses, any mixed assignment where one pair matches on the first coordinate and another matches on the second coordinate forces two distinct points to be equal in both coordinates, yielding a contradiction via Prod.ext. Hence, either all three first coordinates are equal, or all three second coordinates are equal.
uses
Prod.extrcases hpq with h1 | h1 · rcases hpr with h2 | h2 · rcases hqr with h3 | h3 · left; exact ⟨h1, h3⟩ · exfalso; exact dqr (Prod.ext (by omega) h3) · rcases hqr with h3 | h3 · exfalso; exact dpr (Prod.ext (by omega) h2) · exfalso; exact dpq (Prod.ext h1 (by omega)) · rcases hpr with h2 | h2 · rcases hqr with h3 | h3 · exfalso; exact dpq (Prod.ext (by omega) h1) · exfalso; exact dpr (Prod.ext h2 (by omega)) · rcases hqr with h3 | h3 · exfalso; exact dqr (Prod.ext h3 (by omega)) · right; exact ⟨h1, h3⟩
The trace of an AS path cannot contain three distinct points with the same first coordinate.
If three distinct points on an AS trace share their first coordinate, their second coordinates must be strictly distinct, falling into one of six strict total orders. In each order, the difference between the minimum and maximum second coordinates is at least 2, so the corresponding diagonal sum t = x + y increases by at least 2. The two-step growth lemma then forces the first coordinate to increase by at least 1, contradicting the hypothesis that all three first coordinates are identical.
uses
as_dt_path_intersection_le_two_isASPath_step_two,Finset.mem_filter,Prod.extsimp only [asTrace, Finset.mem_filter] at hp hq hr have ap := hp.2; have aq := hq.2; have ar := hr.2 have h_cases : (p.2 < q.2 ∧ q.2 < r.2) ∨ (p.2 < r.2 ∧ r.2 < q.2) ∨ (q.2 < p.2 ∧ p.2 < r.2) ∨ (q.2 < r.2 ∧ r.2 < p.2) ∨ (r.2 < p.2 ∧ p.2 < q.2) ∨ (r.2 < q.2 ∧ q.2 < p.2) := by have dy1 : p.2 ≠ q.2 := fun h => dpq (Prod.ext h1 h) have dy2 : p.2 ≠ r.2 := fun h => dpr (Prod.ext (by omega) h) have dy3 : q.2 ≠ r.2 := fun h => dqr (Prod.ext h2 h) omega rcases h_cases with ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ · have hle : (↑p.1 + ↑p.2 : ℤ) + 2 ≤ ↑r.1 + ↑r.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑p.1 + ↑p.2 : ℤ) + 2 ≤ ↑q.1 + ↑q.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑q.1 + ↑q.2 : ℤ) + 2 ≤ ↑r.1 + ↑r.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑q.1 + ↑q.2 : ℤ) + 2 ≤ ↑p.1 + ↑p.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑r.1 + ↑r.2 : ℤ) + 2 ≤ ↑q.1 + ↑q.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑r.1 + ↑r.2 : ℤ) + 2 ≤ ↑p.1 + ↑p.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega
The trace of a DT path cannot contain three distinct points with the same second coordinate.
Points in the DT trace are clockwise rotations of points in the AS trace. Equal second coordinates n - 1 - x in the DT trace mean that the original points in the AS trace had equal first coordinates x. Three distinct points in the DT trace with identical second coordinates would thus produce three distinct points in the AS trace with identical first coordinates, which was already shown to be impossible.
uses
as_dt_path_intersection_le_two_not_three_same_fst,Finset.mem_image,Finset.mem_filter.mp,Finset.mem_product,Finset.mem_rangesimp only [dtTrace, Finset.mem_image] at hp hq hr obtain ⟨p0, hp0, rfl⟩ := hp obtain ⟨q0, hq0, rfl⟩ := hq obtain ⟨r0, hr0, rfl⟩ := hr have hp0_cb : p0 ∈ chessboard n := (Finset.mem_filter.mp hp0).1 have hq0_cb : q0 ∈ chessboard n := (Finset.mem_filter.mp hq0).1 have hr0_cb : r0 ∈ chessboard n := (Finset.mem_filter.mp hr0).1 simp only [chessboard, Finset.mem_product, Finset.mem_range] at hp0_cb hq0_cb hr0_cb rcases p0 with ⟨px, py⟩ rcases q0 with ⟨qx, qy⟩ rcases r0 with ⟨rx, ry⟩ simp only [rotCW] at h1 h2 dpq dpr dqr have heq1 : px = qx := by omega have heq2 : qx = rx := by omega have d01 : (px, py) ≠ (qx, qy) := by intro h; cases h; exact dpq rfl have d02 : (px, py) ≠ (rx, ry) := by intro h; cases h; exact dpr rfl have d03 : (qx, qy) ≠ (rx, ry) := by intro h; cases h; exact dqr rfl exact as_dt_path_intersection_le_two_not_three_same_fst ha (px, py) (qx, qy) (rx, ry) hp0 hq0 hr0 d01 d02 d03 heq1 heq2
If the intersection of an AS trace and a DT trace has cardinality greater than 2, it contains three pairwise distinct points p, q, and r.
We argue by contradiction. Assuming the cardinality of the intersection is strictly greater than 2, the intersection is nonempty, so we can pick an element p. Erasing p leaves a set of cardinality at least 2, from which we pick q ≠ p. Erasing q leaves a set of cardinality at least 1, from which we choose r distinct from both p and q. Each of p, q, r belongs to both the AS trace and the DT trace.
uses
Finset.card_pos.mp,Finset.card_erase_of_mem,Finset.mem_erase.mp,Finset.mem_inter.mpby_contra hc have hpos1 : 0 < (asTrace n a1 ∩ dtTrace n a2).card := by omega obtain ⟨p, hp⟩ := Finset.card_pos.mp hpos1 have hpos2 : 0 < ((asTrace n a1 ∩ dtTrace n a2).erase p).card := by rw [Finset.card_erase_of_mem hp]; omega obtain ⟨q, hq⟩ := Finset.card_pos.mp hpos2 have hpos3 : 0 < (((asTrace n a1 ∩ dtTrace n a2).erase p).erase q).card := by rw [Finset.card_erase_of_mem hq, Finset.card_erase_of_mem hp]; omega obtain ⟨r, hr⟩ := Finset.card_pos.mp hpos3 have hp_mem : p ∈ asTrace n a1 ∩ dtTrace n a2 := hp have hq_mem : q ∈ asTrace n a1 ∩ dtTrace n a2 := (Finset.mem_erase.mp hq).2 have hr_mem : r ∈ asTrace n a1 ∩ dtTrace n a2 := (Finset.mem_erase.mp (Finset.mem_erase.mp hr).2).2 have dpq : p ≠ q := (Finset.mem_erase.mp hq).1.symm have dpr : p ≠ r := (Finset.mem_erase.mp (Finset.mem_erase.mp hr).2).1.symm have dqr : q ≠ r := (Finset.mem_erase.mp hr).1.symm have hp_as := (Finset.mem_inter.mp hp_mem).1 have hq_as := (Finset.mem_inter.mp hq_mem).1 have hr_as := (Finset.mem_inter.mp hr_mem).1 have hp_dt := (Finset.mem_inter.mp hp_mem).2 have hq_dt := (Finset.mem_inter.mp hq_mem).2 have hr_dt := (Finset.mem_inter.mp hr_mem).2
Every pair of intersection points shares at least one coordinate: p.1 = q.1 ∨ p.2 = q.2, and similarly for (p, r) and (q, r).
For any pair of points in the intersection, their AS trace membership implies their coordinates are ordered in the same direction, while their DT trace membership implies their coordinates are ordered in opposite directions. Combining these constraints forces equality in either the first coordinate (when both ≤ and ≥ hold on the first coordinate) or the second coordinate (when both hold on the second coordinate).
uses
as_dt_path_intersection_le_two_asTrace_order,as_dt_path_intersection_le_two_dtTrace_orderhave hpq : p.1 = q.1 ∨ p.2 = q.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 p q hp_as hq_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 p q hp_dt hq_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega have hpr : p.1 = r.1 ∨ p.2 = r.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 p r hp_as hr_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 p r hp_dt hr_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega have hqr : q.1 = r.1 ∨ q.2 = r.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 q r hq_as hr_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 q r hq_dt hr_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega
The intersection of an AS path trace and a DT path trace contains at most two cells.
By the coordinate-sharing lemma, the three distinct intersection points must either all share their first coordinate or all share their second coordinate. If all three share their first coordinate, they form three points on an AS trace in the same column, contradicting as_dt_path_intersection_le_two_not_three_same_fst. If all three share their second coordinate, they form three points on a DT trace in the same row, contradicting as_dt_path_intersection_le_two_not_three_same_snd_dt. Both cases produce a contradiction, completing the proof.
uses
as_dt_path_intersection_le_two_col_or_row_of_pairwise,as_dt_path_intersection_le_two_not_three_same_fst,as_dt_path_intersection_le_two_not_three_same_snd_dthave hline := as_dt_path_intersection_le_two_col_or_row_of_pairwise p q r hpq hpr hqr dpq dpr dqr rcases hline with ⟨hcol1, hcol2⟩ | ⟨hrow1, hrow2⟩ · exact as_dt_path_intersection_le_two_not_three_same_fst h1 p q r hp_as hq_as hr_as dpq dpr dqr hcol1 hcol2 · exact as_dt_path_intersection_le_two_not_three_same_snd_dt h2 p q r hp_dt hq_dt hr_dt dpq dpr dqr hrow1 hrow2
as_dt_path_intersection_le_two_isASPath_mono- If a is an AS path and t1 ≤ t2, then a(t1) ≤ a(t2).
as_dt_path_intersection_le_two_isASPath_sub_mono- If a is an AS path and t1 ≤ t2, then t1 - a(t1) ≤ t2 - a(t2).
as_dt_path_intersection_le_two_isASPath_step_two- If a is an AS path and t1 + 2 ≤ t2, then a(t1) + 1 ≤ a(t2).
as_dt_path_intersection_le_two_asTrace_order- Any two points on an AS path trace are ordered coordinatewise in the same direction: either both coordinates of the first are at most those of the second, or vice versa.
as_dt_path_intersection_le_two_dtTrace_order- Any two points on a DT path trace are anti-correlated: if the first coordinate increases or stays equal, the second decreases or stays equal.
as_dt_path_intersection_le_two_col_or_row_of_pairwise- Three pairwise distinct points in ℕ × ℕ that pairwise share at least one coordinate must either all share their first coordinate or all share their second coordinate.
as_dt_path_intersection_le_two_not_three_same_fst- An AS path trace cannot contain three distinct points with the same first coordinate.
as_dt_path_intersection_le_two_not_three_same_snd_dt- A DT path trace cannot contain three distinct points with the same second coordinate.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
Finset.mem_filter.mp- If an element belongs to Finset.filter p s, then it belongs to s and satisfies predicate p.
Finset.mem_image- An element belongs to the image of a function on a finite set if and only if it is the image of some element in the set.
Finset.mem_product- A pair belongs to the Cartesian product of two finite sets if and only if each component belongs to the corresponding set.
Finset.mem_range- A natural number belongs to Finset.range n if and only if it is strictly less than n.
Prod.ext- Two pairs are equal if their first components are equal and their second components are equal.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.card_erase_of_mem- Erasing an element from a finite set containing it reduces the cardinality by one.
Finset.mem_erase.mp- An element in s.erase a is distinct from a and belongs to s.
Finset.mem_inter.mp- An element in the intersection of two finite sets belongs to both sets.
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.
lemma as_dt_path_intersection_le_two_isASPath_mono {a : ℤ → ℤ} (h : IsASPath a) {t1 t2 : ℤ} (hle : t1 ≤ t2) : a t1 ≤ a t2 := by obtain ⟨k, rfl⟩ : ∃ k : ℕ, t2 = t1 + k := ⟨(t2 - t1).toNat, by omega⟩ clear hle induction' k with k ih · simp · have hstep : 0 ≤ a (t1 + (k : ℤ) + 1) - a (t1 + (k : ℤ)) := (h (t1 + k)).1 have h1 : a (t1 + (k : ℤ)) ≤ a (t1 + (k + 1 : ℕ)) := by have : (t1 + (k + 1 : ℕ) : ℤ) = t1 + (k : ℤ) + 1 := by push_cast; ring rw [this] linarith have h2 : a t1 ≤ a (t1 + (k : ℤ)) := ih linarithlemma as_dt_path_intersection_le_two_isASPath_sub_mono {a : ℤ → ℤ} (h : IsASPath a) {t1 t2 : ℤ} (hle : t1 ≤ t2) : t1 - a t1 ≤ t2 - a t2 := by obtain ⟨k, rfl⟩ : ∃ k : ℕ, t2 = t1 + k := ⟨(t2 - t1).toNat, by omega⟩ clear hle induction' k with k ih · simp · have hstep : a (t1 + (k : ℤ) + 1) - a (t1 + (k : ℤ)) ≤ 1 := (h (t1 + k)).2.1 have h1 : t1 + (k : ℤ) - a (t1 + (k : ℤ)) ≤ t1 + (k + 1 : ℕ) - a (t1 + (k + 1 : ℕ)) := by have : (t1 + (k + 1 : ℕ) : ℤ) = t1 + (k : ℤ) + 1 := by push_cast; ring rw [this] linarith linarithlemma as_dt_path_intersection_le_two_isASPath_step_two {a : ℤ → ℤ} (h : IsASPath a) {t1 t2 : ℤ} (h2 : t1 + 2 ≤ t2) : a t1 + 1 ≤ a t2 := by have hstep : a t1 + 1 ≤ a (t1 + 2) := (h t1).2.2 have hmono : a (t1 + 2) ≤ a t2 := as_dt_path_intersection_le_two_isASPath_mono h h2 linarithlemma as_dt_path_intersection_le_two_asTrace_order {n : ℕ} {a : ℤ → ℤ} (ha : IsASPath a) (p q : ℕ × ℕ) (hp : p ∈ asTrace n a) (hq : q ∈ asTrace n a) : (p.1 ≤ q.1 ∧ p.2 ≤ q.2) ∨ (q.1 ≤ p.1 ∧ q.2 ≤ p.2) := by simp only [asTrace, Finset.mem_filter] at hp hq have ap := hp.2; have aq := hq.2 have h_cases : (↑p.1 + ↑p.2 : ℤ) ≤ ↑q.1 + ↑q.2 ∨ (↑q.1 + ↑q.2 : ℤ) ≤ ↑p.1 + ↑p.2 := by omega rcases h_cases with hle | hle · left have h1 := as_dt_path_intersection_le_two_isASPath_mono ha hle have h2 := as_dt_path_intersection_le_two_isASPath_sub_mono ha hle constructor <;> omega · right have h1 := as_dt_path_intersection_le_two_isASPath_mono ha hle have h2 := as_dt_path_intersection_le_two_isASPath_sub_mono ha hle constructor <;> omegalemma as_dt_path_intersection_le_two_dtTrace_order {n : ℕ} {a : ℤ → ℤ} (ha : IsASPath a) (p q : ℕ × ℕ) (hp : p ∈ dtTrace n a) (hq : q ∈ dtTrace n a) : (p.1 ≤ q.1 ∧ q.2 ≤ p.2) ∨ (q.1 ≤ p.1 ∧ p.2 ≤ q.2) := by simp only [dtTrace, Finset.mem_image] at hp hq obtain ⟨p0, hp0, rfl⟩ := hp obtain ⟨q0, hq0, rfl⟩ := hq have hp0_cb : p0 ∈ chessboard n := (Finset.mem_filter.mp hp0).1 have hq0_cb : q0 ∈ chessboard n := (Finset.mem_filter.mp hq0).1 simp only [chessboard, Finset.mem_product, Finset.mem_range] at hp0_cb hq0_cb rcases p0 with ⟨px, py⟩ rcases q0 with ⟨qx, qy⟩ simp only [rotCW] have h := as_dt_path_intersection_le_two_asTrace_order ha (px, py) (qx, qy) hp0 hq0 rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · left; constructor <;> omega · right; constructor <;> omegalemma as_dt_path_intersection_le_two_col_or_row_of_pairwise (p q r : ℕ × ℕ) (hpq : p.1 = q.1 ∨ p.2 = q.2) (hpr : p.1 = r.1 ∨ p.2 = r.2) (hqr : q.1 = r.1 ∨ q.2 = r.2) (dpq : p ≠ q) (dpr : p ≠ r) (dqr : q ≠ r) : (p.1 = q.1 ∧ q.1 = r.1) ∨ (p.2 = q.2 ∧ q.2 = r.2) := by rcases hpq with h1 | h1 · rcases hpr with h2 | h2 · rcases hqr with h3 | h3 · left; exact ⟨h1, h3⟩ · exfalso; exact dqr (Prod.ext (by omega) h3) · rcases hqr with h3 | h3 · exfalso; exact dpr (Prod.ext (by omega) h2) · exfalso; exact dpq (Prod.ext h1 (by omega)) · rcases hpr with h2 | h2 · rcases hqr with h3 | h3 · exfalso; exact dpq (Prod.ext (by omega) h1) · exfalso; exact dpr (Prod.ext h2 (by omega)) · rcases hqr with h3 | h3 · exfalso; exact dqr (Prod.ext h3 (by omega)) · right; exact ⟨h1, h3⟩lemma as_dt_path_intersection_le_two_not_three_same_fst {n : ℕ} {a : ℤ → ℤ} (ha : IsASPath a) (p q r : ℕ × ℕ) (hp : p ∈ asTrace n a) (hq : q ∈ asTrace n a) (hr : r ∈ asTrace n a) (dpq : p ≠ q) (dpr : p ≠ r) (dqr : q ≠ r) (h1 : p.1 = q.1) (h2 : q.1 = r.1) : False := by simp only [asTrace, Finset.mem_filter] at hp hq hr have ap := hp.2; have aq := hq.2; have ar := hr.2 have h_cases : (p.2 < q.2 ∧ q.2 < r.2) ∨ (p.2 < r.2 ∧ r.2 < q.2) ∨ (q.2 < p.2 ∧ p.2 < r.2) ∨ (q.2 < r.2 ∧ r.2 < p.2) ∨ (r.2 < p.2 ∧ p.2 < q.2) ∨ (r.2 < q.2 ∧ q.2 < p.2) := by have dy1 : p.2 ≠ q.2 := fun h => dpq (Prod.ext h1 h) have dy2 : p.2 ≠ r.2 := fun h => dpr (Prod.ext (by omega) h) have dy3 : q.2 ≠ r.2 := fun h => dqr (Prod.ext h2 h) omega rcases h_cases with ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ | ⟨hA, hB⟩ · have hle : (↑p.1 + ↑p.2 : ℤ) + 2 ≤ ↑r.1 + ↑r.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑p.1 + ↑p.2 : ℤ) + 2 ≤ ↑q.1 + ↑q.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑q.1 + ↑q.2 : ℤ) + 2 ≤ ↑r.1 + ↑r.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑q.1 + ↑q.2 : ℤ) + 2 ≤ ↑p.1 + ↑p.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑r.1 + ↑r.2 : ℤ) + 2 ≤ ↑q.1 + ↑q.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omega · have hle : (↑r.1 + ↑r.2 : ℤ) + 2 ≤ ↑p.1 + ↑p.2 := by omega have hstep := as_dt_path_intersection_le_two_isASPath_step_two ha hle omegalemma as_dt_path_intersection_le_two_not_three_same_snd_dt {n : ℕ} {a : ℤ → ℤ} (ha : IsASPath a) (p q r : ℕ × ℕ) (hp : p ∈ dtTrace n a) (hq : q ∈ dtTrace n a) (hr : r ∈ dtTrace n a) (dpq : p ≠ q) (dpr : p ≠ r) (dqr : q ≠ r) (h1 : p.2 = q.2) (h2 : q.2 = r.2) : False := by simp only [dtTrace, Finset.mem_image] at hp hq hr obtain ⟨p0, hp0, rfl⟩ := hp obtain ⟨q0, hq0, rfl⟩ := hq obtain ⟨r0, hr0, rfl⟩ := hr have hp0_cb : p0 ∈ chessboard n := (Finset.mem_filter.mp hp0).1 have hq0_cb : q0 ∈ chessboard n := (Finset.mem_filter.mp hq0).1 have hr0_cb : r0 ∈ chessboard n := (Finset.mem_filter.mp hr0).1 simp only [chessboard, Finset.mem_product, Finset.mem_range] at hp0_cb hq0_cb hr0_cb rcases p0 with ⟨px, py⟩ rcases q0 with ⟨qx, qy⟩ rcases r0 with ⟨rx, ry⟩ simp only [rotCW] at h1 h2 dpq dpr dqr have heq1 : px = qx := by omega have heq2 : qx = rx := by omega have d01 : (px, py) ≠ (qx, qy) := by intro h; cases h; exact dpq rfl have d02 : (px, py) ≠ (rx, ry) := by intro h; cases h; exact dpr rfl have d03 : (qx, qy) ≠ (rx, ry) := by intro h; cases h; exact dqr rfl exact as_dt_path_intersection_le_two_not_three_same_fst ha (px, py) (qx, qy) (rx, ry) hp0 hq0 hr0 d01 d02 d03 heq1 heq2/-- An AS path trace and a DT path trace intersect in at most two cells. -/theorem as_dt_path_intersection_le_two (n : ℕ) (a1 a2 : ℤ → ℤ) (h1 : IsASPath a1) (h2 : IsASPath a2) : (asTrace n a1 ∩ dtTrace n a2).card ≤ 2 := by by_contra hc have hpos1 : 0 < (asTrace n a1 ∩ dtTrace n a2).card := by omega obtain ⟨p, hp⟩ := Finset.card_pos.mp hpos1 have hpos2 : 0 < ((asTrace n a1 ∩ dtTrace n a2).erase p).card := by rw [Finset.card_erase_of_mem hp]; omega obtain ⟨q, hq⟩ := Finset.card_pos.mp hpos2 have hpos3 : 0 < (((asTrace n a1 ∩ dtTrace n a2).erase p).erase q).card := by rw [Finset.card_erase_of_mem hq, Finset.card_erase_of_mem hp]; omega obtain ⟨r, hr⟩ := Finset.card_pos.mp hpos3 have hp_mem : p ∈ asTrace n a1 ∩ dtTrace n a2 := hp have hq_mem : q ∈ asTrace n a1 ∩ dtTrace n a2 := (Finset.mem_erase.mp hq).2 have hr_mem : r ∈ asTrace n a1 ∩ dtTrace n a2 := (Finset.mem_erase.mp (Finset.mem_erase.mp hr).2).2 have dpq : p ≠ q := (Finset.mem_erase.mp hq).1.symm have dpr : p ≠ r := (Finset.mem_erase.mp (Finset.mem_erase.mp hr).2).1.symm have dqr : q ≠ r := (Finset.mem_erase.mp hr).1.symm have hp_as := (Finset.mem_inter.mp hp_mem).1 have hq_as := (Finset.mem_inter.mp hq_mem).1 have hr_as := (Finset.mem_inter.mp hr_mem).1 have hp_dt := (Finset.mem_inter.mp hp_mem).2 have hq_dt := (Finset.mem_inter.mp hq_mem).2 have hr_dt := (Finset.mem_inter.mp hr_mem).2 have hpq : p.1 = q.1 ∨ p.2 = q.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 p q hp_as hq_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 p q hp_dt hq_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega have hpr : p.1 = r.1 ∨ p.2 = r.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 p r hp_as hr_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 p r hp_dt hr_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega have hqr : q.1 = r.1 ∨ q.2 = r.2 := by have has := as_dt_path_intersection_le_two_asTrace_order h1 q r hq_as hr_as have hdt := as_dt_path_intersection_le_two_dtTrace_order h2 q r hq_dt hr_dt rcases has with ⟨hA, hB⟩ | ⟨hA, hB⟩ <;> rcases hdt with ⟨hC, hD⟩ | ⟨hC, hD⟩ · right; omega · left; omega · left; omega · right; omega have hline := as_dt_path_intersection_le_two_col_or_row_of_pairwise p q r hpq hpr hqr dpq dpr dqr rcases hline with ⟨hcol1, hcol2⟩ | ⟨hrow1, hrow2⟩ · exact as_dt_path_intersection_le_two_not_three_same_fst h1 p q r hp_as hq_as hr_as dpq dpr dqr hcol1 hcol2 · exact as_dt_path_intersection_le_two_not_three_same_snd_dt h2 p q r hp_dt hq_dt hr_dt dpq dpr dqr hrow1 hrow2