AFTD Auto-Formalizing Theoretical Domains

as_dt_path_intersection_le_two

theoremverifiedformalization

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 than LinearOrder — 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 LinearOrder is a TotalPreorder.

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.

  1. 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).

    lines 2–12

      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
  2. 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).

    lines 16–25

      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
  3. 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.

    lines 28–30

    uses as_dt_path_intersection_le_two_isASPath_mono

      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
      linarith
  4. 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.

    lines 35–46

    uses as_dt_path_intersection_le_two_isASPath_mono, as_dt_path_intersection_le_two_isASPath_sub_mono, Finset.mem_filter

      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 <;> omega
  5. 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.

    lines 51–63

    uses as_dt_path_intersection_le_two_asTrace_order, Finset.mem_image, Finset.mem_filter.mp, Finset.mem_product, Finset.mem_range

      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 <;> omega
  6. 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.

    lines 71–85

    uses Prod.ext

      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⟩
  7. 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.

    lines 91–118

    uses as_dt_path_intersection_le_two_isASPath_step_two, Finset.mem_filter, Prod.ext

      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
        omega
  8. 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.

    lines 124–141

    uses as_dt_path_intersection_le_two_not_three_same_fst, Finset.mem_image, Finset.mem_filter.mp, Finset.mem_product, Finset.mem_range

      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
  9. 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.

    lines 145–165

    uses Finset.card_pos.mp, Finset.card_erase_of_mem, Finset.mem_erase.mp, Finset.mem_inter.mp

      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
  10. 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).

    lines 166–189

    uses as_dt_path_intersection_le_two_asTrace_order, as_dt_path_intersection_le_two_dtTrace_order

      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
  11. 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.

    lines 190–193

    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_dt

      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
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

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
See it in the graphDiscuss this resultChallenge it