AFTD Auto-Formalizing Theoretical Domains

condorcet_bipartite_minimal_private_averaging_obstruction

theoremverified

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.

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

    line 21

        ¬condorcet_bipartite_minimal_private_relation a a := by decide +kernel
  2. 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.

    line 26

          condorcet_bipartite_minimal_private_relation r c := by decide +kernel
  3. 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.

    lines 34–45

    uses of_decide_eq_true

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

    lines 55–64

    uses condorcet_bipartite_minimal_private_members

      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 hsc
  5. 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.

    line 73

        {a,b,c} ∈ condorcet_bipartite_minimal_private_family r := by decide +kernel
  6. For 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.

    lines 84–87

    uses condorcet_bipartite_minimal_private_complete_forward, condorcet_bipartite_minimal_private_complete_backward

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

    line 92

            if b ∈ J then condorcet_bipartite_minimal_private_occupation a else 0 := by decide +kernel
  8. 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.

    line 99

          2 * (∑ a ∈ condorcet_bipartite_minimal_private_set, condorcet_bipartite_minimal_private_weight a) := by decide +kernel
  9. 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.

    line 104

          condorcet_bipartite_minimal_private_order a < condorcet_bipartite_minimal_private_order b := by decide +kernel
  10. 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.

    lines 109–112

    uses measure, condorcet_bipartite_minimal_private_ordered

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

    line 117

        ∃ J ∈ condorcet_bipartite_minimal_private_family a, b ∈ J := by decide +kernel
  12. 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).

    line 135

      decide +kernel
  13. Every 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.

    line 143

      decide +kernel
  14. Every 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.

    lines 147–160

    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_eq

      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]
          tauto
  15. 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.

    lines 166–173

    uses condorcet_bipartite_minimal_private_decode_surj, condorcet_bipartite_minimal_private_check_all, Bool.or_eq_true, Nat.beq_eq

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

    lines 174–179

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

    lines 180–197

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

    line 204

      condorcet_bipartite_minimal_private_color a ≠ condorcet_bipartite_minimal_private_color b := by decide +kernel
  19. 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.

    lines 231–241

    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_wellFounded

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

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

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