condorcet_bipartite_minimal_private_averaging_obstruction
There is an irreflexive15-vertex S3 relation whose only induced S3 subset is the whole graph, every arrow lies in a private triple, and the reciprocal arrows are bipartite. The complete private families admit strictly positive integer occupations with stationary flow3w(b)=sum incoming occupations. Total65016484420889054890 and an induced acyclic set of weight32949241318203599358 violate the half bound. Thus even the bipartite reciprocal-arc restriction combined with global vertex and arc minimality does not repair uniform complete-private averaging.
Statement
theorem condorcet_bipartite_minimal_private_averaging_obstruction : ∃ (R : Fin 15 → Fin 15 → Prop) (F : Fin 15 → Finset (Finset (Fin 15))) (q : Fin 15 → ℕ) (U : Finset (Fin 15)), (∀ a, ¬ R a a) ∧ (∀ a b c, ∃ r, R r a ∧ R r b ∧ R r c) ∧ (∀ a, (F a).Nonempty ∧ ∀ J ∈ F a, J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧ ∀ r, (∀ b ∈ J, R r b) → r = a) ∧ (∀ r a b c, a < b → b < c → ({a,b,c} ∈ F r ↔ R r a ∧ R r b ∧ R r c ∧ ∀ s, (R s a ∧ R s b ∧ R s c) → s = r)) ∧ (∀ B : Finset (Fin 15), (∀ J : Finset (Fin 15), J ⊆ B → J.card ≤ 3 → ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → B = univ) ∧ (∀ a b, R a b → ∃ J ∈ F a, b ∈ J) ∧ (∃ color : Fin 15 → Bool, ∀ a b, R a b → R b a → color a ≠ color b) ∧ (∀ a, 0 < q a) ∧ (∀ b, 3 * ((F b).card * q b) = ∑ a, ∑ J ∈ F a, if b ∈ J then q a else 0) ∧ (∑ a, (F a).card * q a) = 65016484420889054890 ∧ (∑ a ∈ U, (F a).card * q a) = 32949241318203599358 ∧ 0 < (∑ a, (F a).card * q a) ∧ (∑ a, (F a).card * q a) < 2 * (∑ a ∈ U, (F a).card * q a) ∧ WellFounded (fun a b : {a : Fin 15 // a ∈ U} => R a.val b.val)
- Source
- IN-362 finite method diagnostic for OP-19. Strengthens the old bipartite reciprocal-arc example by GLOBAL minimum core and arc minimality. Exact data audited computationally; NOT yet Lean proved. No election counterexample or research advance.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
This theorem provides an obstruction to the conjecture that uniform complete-private averaging satisfies the half-bound, even when restricted to graphs with bipartite reciprocal arcs and no proper induced S3 subgraphs. An explicit 15-vertex irreflexive relation is exhibited and verified to satisfy the S3 property, have stationary flow under strictly positive complete-private occupations, have bipartite reciprocal arcs, and have every arc witness a private triple. Global minimality is proved via an 88-clause bitmask certificate that rules out every proper subset from being an induced S3 subrelation. Finally, an explicit 9-vertex induced subrelation is proved acyclic via a ranking function, yet its stationary occupation weight strictly exceeds half the total weight, refuting the half-bound.
The relation R is irreflexive: no vertex dominates itself. automation
Verified by kernel computation testing that the diagonal bit is zero for all 15 vertices.
¬condorcet_bipartite_minimal_private_relation a a := by decide +kernel
Every triple of vertices in Fin 15 has a common predecessor in R. automation
Verified by kernel evaluation checking all 15^3 triples of vertices.
condorcet_bipartite_minimal_private_relation r c := by decide +kernel
Every vertex has a nonempty family of private triples, each consisting of 3 distinct outgoing neighbors uniquely dominated by that vertex.
Kernel evaluation verifies nonemptiness and checks the property for every triple in the list; we then unpack membership in the finset to conclude that all triples satisfy the private triple condition.
uses
of_decide_eq_truehave hnonempty : ∀ a, (condorcet_bipartite_minimal_private_family a).Nonempty := by decide +kernel have hcheck : ∀ a, (condorcet_bipartite_minimal_private_list a).all (fun J => decide (J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, condorcet_bipartite_minimal_private_relation a b) ∧ ∀ r, (∀ b ∈ J, condorcet_bipartite_minimal_private_relation r b) → r = a)) = true := by decide +kernel intro a refine ⟨hnonempty a, ?_⟩ intro J hJ have hm : J ∈ condorcet_bipartite_minimal_private_list a := by exact List.mem_toFinset.mp hJ exact of_decide_eq_true (List.all_eq_true.mp (hcheck a) J hm)
If {a, b, c} belongs to the private family of r, then r dominates a, b, c and no other vertex dominates all three.
Directly follows by specializing the member characterization of the private family to {a, b, c} and performing a case analysis on elements of the 3-element set.
uses
condorcet_bipartite_minimal_private_membershave hmem := (condorcet_bipartite_minimal_private_members r).2 {a, b, c} hJ refine ⟨hmem.2.2.1 a (by simp), hmem.2.2.1 b (by simp), hmem.2.2.1 c (by simp), ?_⟩ intro s ⟨hsa, hsb, hsc⟩ apply hmem.2.2.2 s intro x hx simp only [mem_insert, mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hsa · exact hsb · exact hsc
For any ordered triple a < b < c, if r is the unique common predecessor of a, b, c, then {a, b, c} belongs to the private family of r. automation
Verified by exhaustive kernel computation over all triples and vertices.
{a,b,c} ∈ condorcet_bipartite_minimal_private_family r := by decide +kernelFor a < b < c, {a, b, c} is in the private family of r if and only if r uniquely dominates a, b, and c.
Combines the forward implication and the backward kernel-evaluated implication into an equivalence.
uses
condorcet_bipartite_minimal_private_complete_forward,condorcet_bipartite_minimal_private_complete_backwardintro r a b c hab hbc constructor · exact condorcet_bipartite_minimal_private_complete_forward r a b c · exact condorcet_bipartite_minimal_private_complete_backward a b c hab hbc r
The occupation weights satisfy the stationary flow equation 3 * w(b) = sum incoming occupations for every vertex b. automation
Verified by direct kernel calculation of the weighted sums for each of the 15 vertices.
if b ∈ J then condorcet_bipartite_minimal_private_occupation a else 0 := by decide +kernel
The total graph weight is 65016484420889054890 and the subset weight is 32949241318203599358, which strictly exceeds half the total weight. automation
Evaluated directly by the kernel on the explicit occupation weights and subset.
2 * (∑ a ∈ condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_weight a) := by decide +kernel
Arcs within the 9-element subset strictly increase the ranking function. automation
Verified by kernel evaluation on all pairs of vertices in the 9-element subset.
condorcet_bipartite_minimal_private_order a < condorcet_bipartite_minimal_private_order b := by decide +kernel
The relation R restricted to the 9-element subset is well-founded (hence acyclic).
Follows by pulling back the standard well-founded order on ℕ via the rank measure, using the fact that arcs in the subset strictly increase the rank.
uses
measure,condorcet_bipartite_minimal_private_orderedrefine (measure (fun a : {a : Fin 15 // a ∈ condorcet_bipartite_minimal_private_set} => condorcet_bipartite_minimal_private_order a.val)).wf.mono ?_ intro a b hab exact condorcet_bipartite_minimal_private_ordered a.val b.val a.property b.property hab
Every directed arc in R belongs to at least one private triple of its source vertex. automation
Verified by kernel evaluation over all 15 × 15 pairs of vertices.
∃ J ∈ condorcet_bipartite_minimal_private_family a, b ∈ J := by decide +kernel
Every 15-bit integer bitmask satisfies the certificate check. automation
Verified by kernel computation splitting the 2^15 search space into high bits (h < 128) and low bits (l < 256).
decide +kernelEvery clause (j, d) in the certificate represents a set J of size at most 3, and d contains all vertices outside J that dominate J. automation
Verified by kernel evaluation over the 88 certificate clauses.
decide +kernelEvery subset of Fin 15 is decoded by some bitmask m < 32768.
Proved by induction on the finite set: the empty set is decoded by 0, and inserting a vertex corresponds to bitwise OR with 2^a, which remains bounded by 2^15.
uses
Finset.induction_on,Nat.pow_lt_pow_right,Nat.or_lt_two_pow,Nat.testBit_lor,Nat.testBit_two_pow,Bool.or_eq_true,decide_eq_true_eqintro B induction B using Finset.induction_on with | empty => exact ⟨0, by norm_num, by ext a; simp [condorcet_bipartite_minimal_private_decode]⟩ | insert a s _ ih => obtain ⟨m, hm, hms⟩ := ih refine ⟨m ||| 2 ^ a.val, ?_, ?_⟩ · have ha : 2 ^ a.val < 2 ^ 15 := Nat.pow_lt_pow_right (by norm_num) a.isLt exact Nat.or_lt_two_pow (by simpa using hm) ha · rw [← hms] ext x simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Nat.testBit_lor, Nat.testBit_two_pow, Bool.or_eq_true, decide_eq_true_eq, Fin.ext_iff] tauto
Any subset B satisfying the 3-element domination condition corresponds to a bitmask m that either equals 32767 or satisfies a certificate clause.
Represent B by its decoded bitmask m, look up the exhaustive certificate check for m via division and modulo by 256, and split into the two cases.
uses
condorcet_bipartite_minimal_private_decode_surj,condorcet_bipartite_minimal_private_check_all,Bool.or_eq_true,Nat.beq_eqintro B hB obtain ⟨m, hm, rfl⟩ := condorcet_bipartite_minimal_private_decode_surj B have hc : condorcet_bipartite_minimal_private_check m = true := by have h := condorcet_bipartite_minimal_private_check_all (m / 256) (by omega) (m % 256) (by omega) rwa [show m / 256 * 256 + m % 256 = m by omega] at h simp only [condorcet_bipartite_minimal_private_check, Bool.or_eq_true, Nat.beq_eq, List.any_eq_true] at hc rcases hc with hfull | ⟨e, he, hok⟩
If the bitmask is m = 32767, then B is the universal set. automation
Substituting m = 32767 and verifying in the kernel that every bit in 32767 is set shows that every vertex belongs to B.
uses
iff_true· subst hfull ext a simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and, iff_true] revert a decide +kernel
If the bitmask m satisfies a certificate clause (j, d), a contradiction arises.
By certificate soundness, J has size at most 3 and is contained in B. The domination hypothesis on B provides a common predecessor a in B outside J. Soundness implies a is set in d, and since a is in B, a is set in m, so a is set in m AND d = j, meaning a is in J, contradicting a not in J.
uses
condorcet_bipartite_minimal_private_cert_sound,Nat.testBit_land,Bool.and_eq_true· exfalso obtain ⟨hcard, hpred⟩ := condorcet_bipartite_minimal_private_cert_sound e he have hJ : condorcet_bipartite_minimal_private_decode e.1 ⊆ condorcet_bipartite_minimal_private_decode m := by intro a ha simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and] at ha ⊢ rw [← hok, Nat.testBit_land] at ha exact (Bool.and_eq_true _ _).mp ha |>.1 obtain ⟨a, haB, haJ, hR⟩ := hB _ hJ hcard have h1 := hpred a haJ hR have h2 : m.testBit a.val = true := by simpa [condorcet_bipartite_minimal_private_decode] using haB apply haJ simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and] rw [← hok, Nat.testBit_land, h1, h2] rfl
The reciprocal arcs of R are bipartite under the explicit 2-coloring. automation
Verified by kernel evaluation checking that whenever R a b and R b a hold, a and b receive different boolean colors.
condorcet_bipartite_minimal_private_color a ≠ condorcet_bipartite_minimal_private_color b := by decide +kernel
The full obstruction exists: an irreflexive 15-vertex S3 relation whose only induced S3 subset is the whole graph, with complete private families, stationary occupations, bipartite reciprocal arcs, and an induced acyclic set exceeding the half-bound.
Instantiates the existential witness with the explicit relation, private families, occupation weights, and 9-element acyclic subset, supplying the previously proved lemmas and pre-computed mass inequalities.
uses
condorcet_bipartite_minimal_private_irreflexive,condorcet_bipartite_minimal_private_s3,condorcet_bipartite_minimal_private_members,condorcet_bipartite_minimal_private_complete,condorcet_bipartite_minimal_private_core,condorcet_bipartite_minimal_private_arc_witness,condorcet_bipartite_minimal_private_coloring,condorcet_bipartite_minimal_private_flow,condorcet_bipartite_minimal_private_mass,condorcet_bipartite_minimal_private_wellFoundedrefine ⟨condorcet_bipartite_minimal_private_relation, condorcet_bipartite_minimal_private_family, condorcet_bipartite_minimal_private_occupation, condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_irreflexive, condorcet_bipartite_minimal_private_s3, condorcet_bipartite_minimal_private_members, condorcet_bipartite_minimal_private_complete, condorcet_bipartite_minimal_private_core, condorcet_bipartite_minimal_private_arc_witness, ⟨condorcet_bipartite_minimal_private_color, condorcet_bipartite_minimal_private_coloring⟩, (by decide +kernel), condorcet_bipartite_minimal_private_flow, ?_, ?_, ?_, ?_, condorcet_bipartite_minimal_private_wellFounded⟩ · exact condorcet_bipartite_minimal_private_mass.1 · exact condorcet_bipartite_minimal_private_mass.2.1 · exact condorcet_bipartite_minimal_private_mass.2.2.1 · exact condorcet_bipartite_minimal_private_mass.2.2.2
of_decide_eq_true- If a decidable proposition evaluates to true, then the proposition holds.
condorcet_bipartite_minimal_private_members- Every vertex has a nonempty family of private triples, each of size 3, containing outgoing neighbors of that vertex, and dominated by no other vertex.
condorcet_bipartite_minimal_private_complete_forward- If a triple belongs to the private family of r, then r dominates all three vertices and no other vertex dominates all three.
condorcet_bipartite_minimal_private_complete_backward- If r uniquely dominates an ordered triple a < b < c, then {a, b, c} belongs to the private family of r.
measure- Constructs a well-founded relation from a ranking function to the natural numbers.
condorcet_bipartite_minimal_private_ordered- Arcs within the designated subset strictly increase the specified ranking order.
Finset.induction_on- Principle of induction for finite sets, starting from the empty set and extending by single elements.
Nat.pow_lt_pow_right- Strict monotonicity of powers with base greater than 1.
Nat.or_lt_two_pow- The bitwise OR of two numbers each less than 2^n is also less than 2^n.
Nat.testBit_lor- The k-th bit of a bitwise OR is the boolean OR of the k-th bits of the operands.
Nat.testBit_two_pow- The m-th bit of 2^n is 1 if and only if n = m.
Bool.or_eq_true- A boolean OR evaluates to true if and only if at least one argument is true.
decide_eq_true_eq- A decidable proposition is equivalent to its boolean reflection equaling true.
condorcet_bipartite_minimal_private_decode_surj- Every subset of Fin 15 is decoded by some bitmask m < 32768.
condorcet_bipartite_minimal_private_check_all- Every bitmask m < 32768 satisfies the certificate check.
Nat.beq_eq- Boolean equality of natural numbers coincides with propositional equality.
iff_true- A proposition is true if and only if it is equivalent to True.
condorcet_bipartite_minimal_private_cert_sound- Every certificate clause (j, d) encodes a set J of size at most 3, and d contains all vertices outside J that dominate J.
Nat.testBit_land- The k-th bit of a bitwise AND is the boolean AND of the k-th bits of the operands.
Bool.and_eq_true- A boolean AND evaluates to true if and only if both arguments are true.
condorcet_bipartite_minimal_private_irreflexive- The relation R is irreflexive.
condorcet_bipartite_minimal_private_s3- Every triple of vertices has a common predecessor in the relation R.
condorcet_bipartite_minimal_private_complete- A triple {a, b, c} with a < b < c is a private triple of r if and only if r is its unique common predecessor.
condorcet_bipartite_minimal_private_core- Any subset satisfying the 3-element common-predecessor property must be the entire graph.
condorcet_bipartite_minimal_private_arc_witness- Every arc in R is contained in at least one private triple of its source vertex.
condorcet_bipartite_minimal_private_coloring- Reciprocal arcs have different colors under the explicit 2-coloring.
condorcet_bipartite_minimal_private_flow- The stationary flow balance 3 * w(b) = sum of incoming occupations holds for every vertex.
condorcet_bipartite_minimal_private_wellFounded- The restriction of R to the designated subset is well-founded (acyclic).
condorcet_bipartite_minimal_private_mass- The total weight and the weight of the acyclic subset, confirming that the acyclic subset has strictly more than half the total weight.
- Several steps rely on kernel decision procedures (`decide +kernel`) to perform exhaustive finite checks, including irreflexivity, the S3 condition on all triples, flow conservation, bipartiteness of reciprocal arcs, and verification of the 88-clause certificate across all 32768 vertex subsets.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 20000000set_option maxRecDepth 20000def condorcet_bipartite_minimal_private_pred : Fin 15 → ℕ := ![16082,16012,9857,24421,30348,16022,14242,523,18619,8303,2463,12299,10041,1035,523]def condorcet_bipartite_minimal_private_relation (a b : Fin 15) : Prop := (condorcet_bipartite_minimal_private_pred b).testBit a.val = trueinstance : DecidableRel condorcet_bipartite_minimal_private_relation := fun a b => inferInstanceAs (Decidable ((condorcet_bipartite_minimal_private_pred b).testBit a.val = true))def condorcet_bipartite_minimal_private_list : Fin 15 → List (Finset (Fin 15)) := ![[{2,3,8},{2,3,9},{2,3,10},{2,3,11},{2,7,8},{2,7,9},{2,7,10},{2,7,11},{2,7,13},{2,8,9},{2,8,11},{2,8,12},{2,8,13},{2,8,14},{2,9,10},{2,9,13},{2,9,14},{2,10,11},{2,10,12},{2,10,13},{2,10,14},{2,11,13},{2,11,14},{2,13,14},{3,7,8},{3,7,9},{3,7,10},{3,7,11},{3,7,13},{3,8,11},{3,8,13},{3,8,14},{3,9,11},{3,9,13},{3,9,14},{3,10,11},{3,10,13},{3,10,14},{3,11,12},{3,11,13},{3,11,14},{3,13,14}],[{0,7,8},{0,7,9},{0,7,10},{0,7,11},{0,7,13},{0,8,9},{0,8,11},{0,8,13},{0,8,14},{0,9,10},{0,9,13},{0,9,14},{0,10,11},{0,10,13},{0,10,14},{0,11,13},{0,11,14},{0,13,14},{5,7,8},{5,7,9},{5,7,10},{5,7,11},{5,7,13},{5,8,9},{5,8,11},{5,8,13},{5,8,14},{5,9,13},{5,9,14},{5,10,11},{5,10,13},{5,10,14},{5,11,13},{5,11,14},{5,13,14},{6,7,8},{6,7,9},{6,7,10},{6,7,11},{6,7,13},{6,8,11},{6,8,13},{6,8,14},{6,9,10},{6,9,13},{6,9,14},{6,10,11},{6,10,13},{6,10,14},{6,11,13},{6,11,14},{6,13,14}],[{1,3,9},{3,4,9},{3,4,10},{3,5,9}],[{1,7,8},{1,7,9},{1,7,10},{1,7,11},{1,7,13},{1,8,9},{1,8,11},{1,8,12},{1,8,13},{1,8,14},{1,9,13},{1,9,14},{1,10,11},{1,10,12},{1,10,13},{1,10,14},{1,11,13},{1,11,14},{1,13,14},{4,7,8},{4,7,9},{4,7,10},{4,7,11},{4,7,13},{4,8,9},{4,8,11},{4,8,12},{4,8,13},{4,8,14},{4,9,13},{4,9,14},{4,10,11},{4,10,12},{4,10,13},{4,10,14},{4,11,13},{4,11,14},{4,13,14}],[{0,8,12},{0,10,12},{5,8,12},{5,10,12}],[{3,6,8},{3,6,9},{6,8,12}],[{0,3,9}],[{0,2,8},{0,2,10},{0,4,8},{0,4,10},{1,2,8},{1,2,10},{1,6,8},{1,6,10},{2,4,8},{2,4,10},{2,5,8},{2,5,10},{2,6,8},{2,6,10},{4,5,8},{4,6,8},{4,6,10}],[{3,6,10},{6,10,12}],[{0,1,7},{0,1,14},{0,2,7},{0,2,14},{0,3,7},{0,3,14},{0,4,7},{0,4,14},{0,7,12},{0,12,14},{1,2,7},{1,2,14},{1,3,7},{1,3,14},{1,5,7},{1,5,14},{1,6,7},{1,6,14},{2,4,7},{2,4,14},{2,5,7},{2,5,14},{2,6,7},{2,6,14},{3,4,7},{3,4,14},{3,5,7},{3,5,14},{3,6,7},{3,6,14},{4,5,7},{4,5,14},{4,6,7},{4,6,14},{5,7,12},{5,12,14},{6,7,12},{6,12,14}],[{0,1,13},{0,2,13},{0,3,13},{0,4,13},{0,12,13},{1,2,13},{1,3,13},{1,5,13},{1,6,13},{2,4,13},{2,5,13},{2,6,13},{3,4,13},{3,5,13},{3,6,13},{4,5,13},{4,6,13},{5,12,13},{6,12,13}],[{0,3,8},{0,3,10},{1,3,8},{3,5,8}],[{0,3,11},{1,3,11},{3,4,11},{3,5,11},{3,6,11}],[{0,1,9},{0,2,9},{0,2,11},{0,4,9},{0,9,12},{0,11,12},{1,2,9},{1,2,11},{1,6,9},{2,4,9},{2,4,11},{2,5,9},{2,5,11},{2,6,9},{2,6,11},{4,6,9},{5,9,12},{5,11,12},{6,11,12}],[{3,4,8}]]def condorcet_bipartite_minimal_private_family (a : Fin 15) : Finset (Finset (Fin 15)) := (condorcet_bipartite_minimal_private_list a).toFinsetdef condorcet_bipartite_minimal_private_occupation : Fin 15 → ℕ := ![122302088000489630,70610140282895734,734812011212854860,245816903459202084,1138701283410615507,1075808512214415316,4986221101208269346,140159060107615556,2670517002872160086,126724739297265274,265882714522224420,888759696569514400,810094822257257864,188424245588257680,2382704021829464452]def condorcet_bipartite_minimal_private_weight (a : Fin 15) : ℕ := (condorcet_bipartite_minimal_private_family a).card * condorcet_bipartite_minimal_private_occupation adef condorcet_bipartite_minimal_private_order : Fin 15 → ℕ := ![0,0,2,0,5,6,8,0,7,0,0,3,0,1,4]def condorcet_bipartite_minimal_private_set : Finset (Fin 15) := {7,13,2,11,14,4,5,8,6}theorem condorcet_bipartite_minimal_private_irreflexive : ∀ a, ¬condorcet_bipartite_minimal_private_relation a a := by decide +kerneltheorem condorcet_bipartite_minimal_private_s3 : ∀ a b c : Fin 15, ∃ r, condorcet_bipartite_minimal_private_relation r a ∧ condorcet_bipartite_minimal_private_relation r b ∧ condorcet_bipartite_minimal_private_relation r c := by decide +kerneltheorem condorcet_bipartite_minimal_private_members : ∀ a, (condorcet_bipartite_minimal_private_family a).Nonempty ∧ ∀ J ∈ condorcet_bipartite_minimal_private_family a, J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, condorcet_bipartite_minimal_private_relation a b) ∧ ∀ r, (∀ b ∈ J, condorcet_bipartite_minimal_private_relation r b) → r = a := by have hnonempty : ∀ a, (condorcet_bipartite_minimal_private_family a).Nonempty := by decide +kernel have hcheck : ∀ a, (condorcet_bipartite_minimal_private_list a).all (fun J => decide (J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, condorcet_bipartite_minimal_private_relation a b) ∧ ∀ r, (∀ b ∈ J, condorcet_bipartite_minimal_private_relation r b) → r = a)) = true := by decide +kernel intro a refine ⟨hnonempty a, ?_⟩ intro J hJ have hm : J ∈ condorcet_bipartite_minimal_private_list a := by exact List.mem_toFinset.mp hJ exact of_decide_eq_true (List.all_eq_true.mp (hcheck a) J hm)theorem condorcet_bipartite_minimal_private_complete_forward (r a b c : Fin 15) (hJ : {a, b, c} ∈ condorcet_bipartite_minimal_private_family r) : condorcet_bipartite_minimal_private_relation r a ∧ condorcet_bipartite_minimal_private_relation r b ∧ condorcet_bipartite_minimal_private_relation r c ∧ ∀ s, (condorcet_bipartite_minimal_private_relation s a ∧ condorcet_bipartite_minimal_private_relation s b ∧ condorcet_bipartite_minimal_private_relation s c) → s = r := by have hmem := (condorcet_bipartite_minimal_private_members r).2 {a, b, c} hJ refine ⟨hmem.2.2.1 a (by simp), hmem.2.2.1 b (by simp), hmem.2.2.1 c (by simp), ?_⟩ intro s ⟨hsa, hsb, hsc⟩ apply hmem.2.2.2 s intro x hx simp only [mem_insert, mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hsa · exact hsb · exact hsctheorem condorcet_bipartite_minimal_private_complete_backward : ∀ a b c : Fin 15, a < b → b < c → ∀ r, (condorcet_bipartite_minimal_private_relation r a ∧ condorcet_bipartite_minimal_private_relation r b ∧ condorcet_bipartite_minimal_private_relation r c ∧ ∀ s, (condorcet_bipartite_minimal_private_relation s a ∧ condorcet_bipartite_minimal_private_relation s b ∧ condorcet_bipartite_minimal_private_relation s c) → s = r) → {a,b,c} ∈ condorcet_bipartite_minimal_private_family r := by decide +kerneltheorem condorcet_bipartite_minimal_private_complete : ∀ r a b c : Fin 15, a < b → b < c → ({a,b,c} ∈ condorcet_bipartite_minimal_private_family r ↔ condorcet_bipartite_minimal_private_relation r a ∧ condorcet_bipartite_minimal_private_relation r b ∧ condorcet_bipartite_minimal_private_relation r c ∧ ∀ s, (condorcet_bipartite_minimal_private_relation s a ∧ condorcet_bipartite_minimal_private_relation s b ∧ condorcet_bipartite_minimal_private_relation s c) → s = r) := by intro r a b c hab hbc constructor · exact condorcet_bipartite_minimal_private_complete_forward r a b c · exact condorcet_bipartite_minimal_private_complete_backward a b c hab hbc rtheorem condorcet_bipartite_minimal_private_flow : ∀ b : Fin 15, 3 * condorcet_bipartite_minimal_private_weight b = ∑ a : Fin 15, ∑ J ∈ condorcet_bipartite_minimal_private_family a, if b ∈ J then condorcet_bipartite_minimal_private_occupation a else 0 := by decide +kerneltheorem condorcet_bipartite_minimal_private_mass : (∑ a : Fin 15, condorcet_bipartite_minimal_private_weight a) = 65016484420889054890 ∧ (∑ a ∈ condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_weight a) = 32949241318203599358 ∧ 0 < (∑ a : Fin 15, condorcet_bipartite_minimal_private_weight a) ∧ (∑ a : Fin 15, condorcet_bipartite_minimal_private_weight a) < 2 * (∑ a ∈ condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_weight a) := by decide +kerneltheorem condorcet_bipartite_minimal_private_ordered : ∀ a b : Fin 15, a ∈ condorcet_bipartite_minimal_private_set → b ∈ condorcet_bipartite_minimal_private_set → condorcet_bipartite_minimal_private_relation a b → condorcet_bipartite_minimal_private_order a < condorcet_bipartite_minimal_private_order b := by decide +kerneltheorem condorcet_bipartite_minimal_private_wellFounded : WellFounded (fun a b : {a : Fin 15 // a ∈ condorcet_bipartite_minimal_private_set} => condorcet_bipartite_minimal_private_relation a.val b.val) := by refine (measure (fun a : {a : Fin 15 // a ∈ condorcet_bipartite_minimal_private_set} => condorcet_bipartite_minimal_private_order a.val)).wf.mono ?_ intro a b hab exact condorcet_bipartite_minimal_private_ordered a.val b.val a.property b.property habtheorem condorcet_bipartite_minimal_private_arc_witness : ∀ a b : Fin 15, condorcet_bipartite_minimal_private_relation a b → ∃ J ∈ condorcet_bipartite_minimal_private_family a, b ∈ J := by decide +kernel/-- Clauses `(j, d)`: `j` is the mask of a set `J` of at most three vertices and `d` adds toit every vertex outside `J` that precedes all of `J`. A vertex mask `m` with`m &&& d = j` contains `J` and no such predecessor, so it violates the closure hypothesis at `J`. -/def condorcet_bipartite_minimal_private_cert : List (ℕ × ℕ) := [(129, 643), (130, 650), (260, 389), (136, 649), (515, 8707), (641, 643), (644, 645), (8195, 9219), (1029, 1157), (536, 540), (8224, 9250), (1090, 1218), (128, 651), (16393, 16905), (8706, 8714), (1028, 1157), (1040, 1180), (16960, 16962), (8200, 9225), (6176, 14368), (522, 526), (514, 8718), (8193, 9219), (16386, 16906), (131, 643), (16392, 16905), (640, 651), (5, 9861), (513, 8771), (9248, 9250), (320, 482), (516, 8709), (544, 8742), (16384, 16907), (1033, 3081), (2056, 6153), (2057, 6153), (8192, 9227), (4, 9861), (8194, 9226), (5121, 5137), (9224, 9225), (16385, 16899), (16, 30364), (576, 8802), (280, 16664), (512, 8815), (4098, 13834), (520, 621), (4106, 5642), (1088, 1474), (288, 2482), (66, 14018), (1026, 3214), (9216, 9227), (3074, 3082), (4112, 13848), (2080, 14370), (4097, 13841), (1032, 3341), (40, 7724), (9217, 9219), (4120, 5656), (517, 8709), (6152, 6153), (2, 16014), (64, 14306), (2050, 14346), (264, 18729), (9, 7753), (521, 585), (6144, 14345), (8, 24429), (32, 16054), (256, 18875), (1024, 3487), (2048, 14347), (2049, 14339), (4128, 13872), (1041, 1169), (1096, 1352), (1025, 3219), (1, 16083), (4096, 14137), (4104, 5929), (266, 2314), (0, 32767), (328, 360)]/-- The vertex set encoded by the bits of `m`. -/def condorcet_bipartite_minimal_private_decode (m : ℕ) : Finset (Fin 15) := Finset.univ.filter (fun a : Fin 15 => m.testBit a.val = true)/-- Every mask but the full one meets some clause. -/def condorcet_bipartite_minimal_private_check (m : ℕ) : Bool := m.beq 32767 || condorcet_bipartite_minimal_private_cert.any (fun e => (m &&& e.2).beq e.1)theorem condorcet_bipartite_minimal_private_check_all : ∀ h < 128, ∀ l < 256, condorcet_bipartite_minimal_private_check (h * 256 + l) = true := by decide +kerneltheorem condorcet_bipartite_minimal_private_cert_sound : ∀ e ∈ condorcet_bipartite_minimal_private_cert, (condorcet_bipartite_minimal_private_decode e.1).card ≤ 3 ∧ ∀ a : Fin 15, a ∉ condorcet_bipartite_minimal_private_decode e.1 → (∀ b ∈ condorcet_bipartite_minimal_private_decode e.1, condorcet_bipartite_minimal_private_relation a b) → e.2.testBit a.val = true := by decide +kerneltheorem condorcet_bipartite_minimal_private_decode_surj : ∀ B : Finset (Fin 15), ∃ m < 32768, condorcet_bipartite_minimal_private_decode m = B := by intro B induction B using Finset.induction_on with | empty => exact ⟨0, by norm_num, by ext a; simp [condorcet_bipartite_minimal_private_decode]⟩ | insert a s _ ih => obtain ⟨m, hm, hms⟩ := ih refine ⟨m ||| 2 ^ a.val, ?_, ?_⟩ · have ha : 2 ^ a.val < 2 ^ 15 := Nat.pow_lt_pow_right (by norm_num) a.isLt exact Nat.or_lt_two_pow (by simpa using hm) ha · rw [← hms] ext x simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Nat.testBit_lor, Nat.testBit_two_pow, Bool.or_eq_true, decide_eq_true_eq, Fin.ext_iff] tautotheorem condorcet_bipartite_minimal_private_core : ∀ B : Finset (Fin 15), (∀ J : Finset (Fin 15), J ⊆ B → J.card ≤ 3 → ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, condorcet_bipartite_minimal_private_relation a b) → B = Finset.univ := by intro B hB obtain ⟨m, hm, rfl⟩ := condorcet_bipartite_minimal_private_decode_surj B have hc : condorcet_bipartite_minimal_private_check m = true := by have h := condorcet_bipartite_minimal_private_check_all (m / 256) (by omega) (m % 256) (by omega) rwa [show m / 256 * 256 + m % 256 = m by omega] at h simp only [condorcet_bipartite_minimal_private_check, Bool.or_eq_true, Nat.beq_eq, List.any_eq_true] at hc rcases hc with hfull | ⟨e, he, hok⟩ · subst hfull ext a simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and, iff_true] revert a decide +kernel · exfalso obtain ⟨hcard, hpred⟩ := condorcet_bipartite_minimal_private_cert_sound e he have hJ : condorcet_bipartite_minimal_private_decode e.1 ⊆ condorcet_bipartite_minimal_private_decode m := by intro a ha simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and] at ha ⊢ rw [← hok, Nat.testBit_land] at ha exact (Bool.and_eq_true _ _).mp ha |>.1 obtain ⟨a, haB, haJ, hR⟩ := hB _ hJ hcard have h1 := hpred a haJ hR have h2 : m.testBit a.val = true := by simpa [condorcet_bipartite_minimal_private_decode] using haB apply haJ simp only [condorcet_bipartite_minimal_private_decode, Finset.mem_filter, Finset.mem_univ, true_and] rw [← hok, Nat.testBit_land, h1, h2] rfldef condorcet_bipartite_minimal_private_color : Fin 15 → Bool := ![false,false,false,false,false,false,false,true,true,true,true,true,true,true,true]theorem condorcet_bipartite_minimal_private_coloring : ∀ a b : Fin 15, condorcet_bipartite_minimal_private_relation a b → condorcet_bipartite_minimal_private_relation b a → condorcet_bipartite_minimal_private_color a ≠ condorcet_bipartite_minimal_private_color b := by decide +kerneltheorem condorcet_bipartite_minimal_private_averaging_obstruction : ∃ (R : Fin 15 → Fin 15 → Prop) (F : Fin 15 → Finset (Finset (Fin 15))) (q : Fin 15 → ℕ) (U : Finset (Fin 15)), (∀ a, ¬ R a a) ∧ (∀ a b c, ∃ r, R r a ∧ R r b ∧ R r c) ∧ (∀ a, (F a).Nonempty ∧ ∀ J ∈ F a, J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧ ∀ r, (∀ b ∈ J, R r b) → r = a) ∧ (∀ r a b c, a < b → b < c → ({a,b,c} ∈ F r ↔ R r a ∧ R r b ∧ R r c ∧ ∀ s, (R s a ∧ R s b ∧ R s c) → s = r)) ∧ (∀ B : Finset (Fin 15), (∀ J : Finset (Fin 15), J ⊆ B → J.card ≤ 3 → ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → B = univ) ∧ (∀ a b, R a b → ∃ J ∈ F a, b ∈ J) ∧ (∃ color : Fin 15 → Bool, ∀ a b, R a b → R b a → color a ≠ color b) ∧ (∀ a, 0 < q a) ∧ (∀ b, 3 * ((F b).card * q b) = ∑ a, ∑ J ∈ F a, if b ∈ J then q a else 0) ∧ (∑ a, (F a).card * q a) = 65016484420889054890 ∧ (∑ a ∈ U, (F a).card * q a) = 32949241318203599358 ∧ 0 < (∑ a, (F a).card * q a) ∧ (∑ a, (F a).card * q a) < 2 * (∑ a ∈ U, (F a).card * q a) ∧ WellFounded (fun a b : {a : Fin 15 // a ∈ U} => R a.val b.val) := by refine ⟨condorcet_bipartite_minimal_private_relation, condorcet_bipartite_minimal_private_family, condorcet_bipartite_minimal_private_occupation, condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_irreflexive, condorcet_bipartite_minimal_private_s3, condorcet_bipartite_minimal_private_members, condorcet_bipartite_minimal_private_complete, condorcet_bipartite_minimal_private_core, condorcet_bipartite_minimal_private_arc_witness, ⟨condorcet_bipartite_minimal_private_color, condorcet_bipartite_minimal_private_coloring⟩, (by decide +kernel), condorcet_bipartite_minimal_private_flow, ?_, ?_, ?_, ?_, condorcet_bipartite_minimal_private_wellFounded⟩ · exact condorcet_bipartite_minimal_private_mass.1 · exact condorcet_bipartite_minimal_private_mass.2.1 · exact condorcet_bipartite_minimal_private_mass.2.2.1 · exact condorcet_bipartite_minimal_private_mass.2.2.2