Alphabeta MathHow 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.
Eventown: distinct with every and every even satisfy
Statement
Let be distinct subsets of . If every is even and every intersection with is even, then
Facts & Assumptions
Given: distinct subsets with every even and every even for .
Over , the standard-form values of all the incidence vectors vanish against one another and against themselves ( is the image of in ; over it is or according to the parity of ).
For a subspace , one has (For a subspace , , where ).
A -dimensional vector space over has elements (A -dimensional vector space over a field with elements has exactly elements).
Proof
Work over , and let be the span of the incidence vectors . By [L1], every pairing is .
Bilinearity then gives for all , so .
Writing , the inclusion of step 2.1 and [L2] give . Hence , so .
The distinct incidence vectors lie in , so . By [L3], , and therefore .
Remarks
- The floor enters only because is an integer and . The proof is otherwise the same in both parities of .
Depends on
- Oddtown: distinct $A_1,\dots,A_m\subseteq[n]$ with every $\lvert A_i\rvert$ odd and every $\lvert A_i\cap A_j\rvert$ ($i\ne j$) even satisfy $m\le n$
- $\langle v_A,v_B\rangle$ is the image of $\lvert A\cap B\rvert$ in $F$; over $\mathbb{F}_2$ it is $0$ or $1$ according to the parity of $\lvert A\cap B\rvert$
- For a subspace $U\le F^{n}$, $\dim_F U^{\perp}=n-\dim_F U$, where $U^{\perp}=\{x:\langle x,u\rangle=0\text{ for all }u\in U\}$
- A $d$-dimensional vector space over a field with $q$ elements has exactly $q^{d}$ elements
- Linear combination of a finite list, and the span $\operatorname{span}(S)$ as the smallest linear subspace containing $S$
- Linear subspace of a vector space
- For every prime $p$, the two operations on $\mathbb{Z}/p$ make it a field
- A finite family of subsets of $[n]$ and its incidence matrix over $F$
- The standard bilinear form $\langle x,y\rangle=\sum_{i<n}x_iy_i$ on $F^{n}$
Used by
- The pairing construction gives an Eventown family of size 2^⌊ n/2⌋ Example
- FALSE: distinct nonempty A₁,…,Aₘ⊆[n] whose pairwise intersections all have the same parity satisfy m≤ n False statement
- Which field each bound is proved over, and what changes when it is replaced Remark
- An Eventown family that no further set can be added to has exactly 2^⌊ n/2⌋ members Theorem
Dependency tree · two levels
48 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, §2.3.2 (standard reference, not scraped)
- O. Pikhurko, An Introduction to Combinatorics, §4.2 (standard reference, not scraped)