TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Oddtown: distinct $A_{1}, \dots, A_{m} \subseteq [n]$ with every $∣ A_{i} ∣$ odd and every $∣ A_{i} \cap A_{j} ∣$ ( $i \neq j$ ) even satisfy $m \leq n$

Statement

Let $A_{1}, \dots, A_{m}$ be distinct subsets of $[n]$ . If every $∣ A_{i} ∣$ is odd and every intersection $∣ A_{i} \cap A_{j} ∣$ with $i \neq j$ is even, then $m \leq n$ .

Facts & Assumptions

Given: distinct subsets $A_{1}, \dots, A_{m} \subseteq [n]$ with every $∣ A_{i} ∣$ odd and every $∣ A_{i} \cap A_{j} ∣$ even for $i \neq j$ .

[F1]

$Z / 2$ is a field (For every prime $p$ , the two operations on $Z / p$ make it a field, The congruence class $[a]_{n}$ and the quotient set $Z / n$ ).

[L1]

Over $F_{2}$ , the pairing $⟨ v_{A}, v_{B} ⟩$ is $1$ exactly when $∣ A \cap B ∣$ is odd and $0$ exactly when it is even ( $⟨ v_{A}, v_{B} ⟩$ is the image of $∣ A \cap B ∣$ in $F$ ; over $F_{2}$ it is $0$ or $1$ according to the parity of $∣ A \cap B ∣$ ).

[L2]

If vectors $v_{i}, w_{i}$ in a bilinear space satisfy $⟨ v_{i}, w_{i} ⟩ \neq 0$ and $⟨ v_{i}, w_{j} ⟩ = 0$ for $i \neq j$ , then the vectors $v_{i}$ are linearly independent (Diagonal criterion: if $⟨ v_{i}, w_{i} ⟩ \neq 0$ and $⟨ v_{i}, w_{j} ⟩ = 0$ for $i \neq j$ , then $v_{1}, \dots, v_{m}$ are linearly independent).

[L3]

A family with independent incidence vectors has at most $n$ members (If the incidence vectors of $A_{1}, \dots, A_{m} \subseteq [n]$ are linearly independent over $F$ then $m \leq n$ ).

Proof

technique · direct

1.1F1L1given

Work over $F_{2}$ , which is a field by [F1]. Then [L1] turns the parity hypotheses into $⟨ v_{A_{i}}, v_{A_{i}} ⟩ = 1, ⟨ v_{A_{i}}, v_{A_{j}} ⟩ = 0 for i \neq j .$

2.1L2step 1.1

This is exactly the diagonal criterion with $w_{i} = v_{A_{i}}$ , so the vectors $v_{A_{1}}, \dots, v_{A_{m}}$ are linearly independent over $F_{2}$ by [L2].

3.1L3step 2.1∎

The master lemma [L3] now gives $m \leq n$ .

Remarks

The argument uses the standard bilinear form on $F_{2}^{n}$ , not an inner product. Bilinearity and the diagonal pattern are enough.

Depends on

Used by

Dependency tree · two levels

30 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, §1.1 (standard reference, not scraped)
J. Matousek, Thirty-three Miniatures, Miniature 3 (standard reference, not scraped)
O. Pikhurko, An Introduction to Combinatorics, §4.1 (standard reference, not scraped)

Oddtown: distinct A1,…,Am⊆[n]A1​,…,Am​⊆[n] with every ∣Ai∣∣Ai​∣ odd and every ∣Ai∩Aj∣∣Ai​∩Aj​∣ (i≠ji=j) even satisfy m≤nm≤n