open_problem_line_cubic_t_count
theoremverifiedoriginal
For every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
Statement
theorem open_problem_line_cubic_t_count (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (line_syndrome n) ∧ S.card = 2 * n + 1- Related work
- arXiv:2610.01024, Appendix K.2, item 1 (open problem: the general case beyond the witnesses through n = 12)
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- line_syndromeThe syndrome of the line cubic form assigns 1 to adjacent triples {i, i+1, i+2} and 0 to all other subsets of Fin n.
- is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
- line_cubic_nat_family_existsEvery n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
Read back from the Lean
For every natural number $n \ge 5$, there exists a family $S$ of distinct nonempty subsets of $\mathrm{Fin}(n)$ such that $|S| = 2n + 1$, and for every subset $A \subseteq \mathrm{Fin}(n)$ with $1 \le |A| \le 3$, the number of sets $y \in S$ that contain $A$ is odd if $A = \{i, i+1, i+2\}$ for some $i \in \{0, \dots, n-3\}$, and even otherwise.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
set_option maxHeartbeats 4000000 set_option maxRecDepth 4096 namespace LineBuild open Finset noncomputable def target (n : ℕ) (A : Finset ℕ) : ZMod 2 := by classical exact if ∃ t, t+2 < n ∧ A = {t,t+1,t+2} then 1 else 0 theorem target_small (n : ℕ) (A : Finset ℕ) (hc : A.card < 3) : target n A = 0 := by unfold target apply if_neg rintro ⟨t,ht,rfl⟩ have he : ({t,t+1,t+2} : Finset ℕ).card = 3 := by simp <;> omega omega theorem target_three (n i j k : ℕ) (hk : k < n) (hj : j < k) (hi : i < j) : target n {i,j,k} = if j=i+1 ∧ k=i+2 then 1 else 0 := by unfold target have he : (∃ t, t+2 < n ∧ ({i,j,k} : Finset ℕ) = {t,t+1,t+2}) ↔ j=i+1 ∧ k=i+2 := by constructor · rintro ⟨t,ht,he⟩ have h1 : i ∈ ({t,t+1,t+2} : Finset ℕ) := he ▸ (by simp) have h2 : j ∈ ({t,t+1,t+2} : Finset ℕ) := he ▸ (by simp) have h3 : k ∈ ({t,t+1,t+2} : Finset ℕ) := he ▸ (by simp) have h4 : t ∈ ({i,j,k} : Finset ℕ) := he.symm ▸ (by simp) have h5 : t+2 ∈ ({i,j,k} : Finset ℕ) := he.symm ▸ (by simp) simp only [mem_insert,mem_singleton] at h1 h2 h3 h4 h5 omega · rintro ⟨rfl,rfl⟩ exact ⟨i,hk,rfl⟩ simp only [he] theorem good_moment (n : ℕ) (S : Finset (Finset ℕ)) (h : Good n S) (A : Finset ℕ) (hb : ∀ i ∈ A, i < n) (hc : 1 ≤ A.card ∧ A.card ≤ 3) : moment S A = target n A := by have hcases : A.card = 1 ∨ A.card = 2 ∨ A.card = 3 := by omega rcases hcases with hc | hc | hc · obtain ⟨i,rfl⟩ := card_eq_one.mp hc rw [h.one i (hb i (by simp)), target_small n {i} (by simp)] · let f := A.orderEmbOfFin hc have he : A = {f 0,f 1} := by calc A = image f univ := (A.image_orderEmbOfFin_univ hc).symm _ = {f 0,f 1} := by rw [show (univ : Finset (Fin 2)) = {0,1} by decide] simp have hlt : f 0 < f 1 := f.strictMono (by decide) have hfn : f 1 < n := hb _ (A.orderEmbOfFin_mem hc 1) rw [he, h.two (f 1) hfn (f 0) hlt, target_small n {f 0,f 1}] simp <;> omega · let f := A.orderEmbOfFin hc have he : A = {f 0,f 1,f 2} := by calc A = image f univ := (A.image_orderEmbOfFin_univ hc).symm _ = {f 0,f 1,f 2} := by rw [show (univ : Finset (Fin 3)) = {0,1,2} by decide] simp have h01 : f 0 < f 1 := f.strictMono (by decide) have h12 : f 1 < f 2 := f.strictMono (by decide) have hfn : f 2 < n := hb _ (A.orderEmbOfFin_mem hc 2) rw [he, h.three (f 2) hfn (f 1) h12 (f 0) h01, target_three n (f 0) (f 1) (f 2) hfn h12 h01] def pack (n : ℕ) (y : Finset ℕ) : Finset (Fin n) := univ.filter (fun i => i.val ∈ y) theorem pack_image (n : ℕ) (y : Finset ℕ) (hb : ∀ i ∈ y, i < n) : (pack n y).image Fin.val = y := by ext i simp only [mem_image, pack, mem_filter, mem_univ, true_and] constructor · rintro ⟨j,hj,rfl⟩; exact hj · intro hi; exact ⟨⟨i,hb i hi⟩,hi,rfl⟩ theorem pack_subset (n : ℕ) (A : Finset (Fin n)) (y : Finset ℕ) : A ⊆ pack n y ↔ A.image Fin.val ⊆ y := by simp only [subset_iff, pack, mem_filter, mem_univ, true_and] constructor · rintro h i hi obtain ⟨j,hj,rfl⟩ := mem_image.mp hi exact h hj · intro h i hi exact h (mem_image.mpr ⟨i,hi,rfl⟩) theorem target_fin (n : ℕ) (A : Finset (Fin n)) : target n (A.image Fin.val) = line_syndrome n A := by unfold target line_syndrome have he : (∃ t, t+2 < n ∧ A.image Fin.val = {t,t+1,t+2}) ↔ ∃ i : Fin (n-2), A = {⟨i.val,by omega⟩,⟨i.val+1,by omega⟩,⟨i.val+2,by omega⟩} := by constructor · rintro ⟨t,ht,he⟩ refine ⟨⟨t,by omega⟩,?_⟩ apply Finset.image_injective Fin.val_injective simpa only [image_insert,image_singleton] using he · rintro ⟨i,rfl⟩ refine ⟨i.val,by omega,?_⟩ simp only [image_insert,image_singleton] simp only [he] theorem good_repr (n : ℕ) (S : Finset (Finset ℕ)) (h : Good n S) : ∃ T : Finset (Finset (Fin n)), is_parity_repr T (line_syndrome n) ∧ T.card = 2*n+1 := by classical have hinj : Set.InjOn (pack n) (↑S : Set (Finset ℕ)) := by intro x hx y hy he have hh := congrArg (image Fin.val) he simpa only [pack_image n x (h.bounded x hx), pack_image n y (h.bounded y hy)] using hh refine ⟨S.image (pack n), ⟨?_,?_⟩,?_⟩ · intro y hy obtain ⟨z,hz,rfl⟩ := mem_image.mp hy obtain ⟨i,hi⟩ := h.nonempty z hz exact ⟨⟨i,h.bounded z hz i hi⟩,by simp [pack,hi]⟩ · intro A hA rw [Finset.natCast_card_filter, sum_image hinj] have he : (∑ y ∈ S, if A ⊆ pack n y then (1 : ZMod 2) else 0) = moment S (A.image Fin.val) := by simp only [moment,chi,pack_subset] rw [he,good_moment n S h (A.image Fin.val),target_fin] · intro i hi obtain ⟨j,hj,rfl⟩ := mem_image.mp hi exact j.isLt · simpa only [card_image_of_injective _ Fin.val_injective] using hA · rw [card_image_of_injOn hinj, h.size] end LineBuild /-- Open Problem 4: whether the line family attains T-count 2n + 1 for every n ≥ 5. -/ theorem open_problem_line_cubic_t_count (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (line_syndrome n) ∧ S.card = 2 * n + 1 := by obtain ⟨S,hS⟩ := line_cubic_nat_family_exists n hn exact LineBuild.good_repr n S hS