Erdős Problem #723

Erdős Problem 723 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: falsifiable. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/723.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Fix an integer $n\ge 1$. Let $P$ be a set of size \[ |P| = n^2+n+1. \] A finite projective plane of order $n$ (as defined in the problem statement) is a collection $\mathcal L$ of subsets of $P$ (called lines) such that:

(a) Every line has size $n+1$: for all $L\in\mathcal L$, $|L|=n+1$.

(b) Every unordered pair of distinct points lies on exactly one line: for all distinct $x,y\in P$, there exists a unique $L\in\mathcal L$ with $\{x,y\}\subseteq L$.

Question: If such $(P,\mathcal L)$ exists, must $n$ be a prime power (i.e. $n=p^m$ for some prime $p$ and integer $m\ge 1$)?

Edge cases/conventions: The definition makes sense for $n=1$ and gives a non-degenerate structure. We do not consider $n=0$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records:

- Constructions exist whenever $n$ is a prime power. - The conjecture is verified for $n\le 11$. - It is open whether a projective plane of order $12$ exists. - (Bruck--Ryser) If $n\equiv 1\pmod 4$ or $n\equiv 2\pmod 4$, then $n$ must be a sum of two squares (e.g. this rules out $n=6,14$). - The case $n=10$ was ruled out by computer search.

I do not use any facts beyond what is explicitly stated above.

3) ATTACK PLAN

Proof track ideas (unlikely to close here): - Extract algebraic structure from incidences (coordinate the plane) and force a finite field of size $n$. - Use strong arithmetic constraints on incidence matrices (eigenvalues, $p$-ranks) to force prime-power order.

Disproof track ideas: - Try to construct an explicit incidence structure of order $n$ for a non-prime-power $n$ (smallest candidate is $n=12$).

Given the status, I focus on rigorous internal consequences of the given axioms and small-case verification.

4) WORK

FAST REALITY CHECK.

I verified by explicit construction (and a short script) that projective planes of order $n=1,2,3$ exist:

- $n=1$: $P=\{1,2,3\}$ and $\mathcal L=\{\{1,2\},\{1,3\},\{2,3\}\}$. - $n=2$: the Fano plane on $P=\{1,\dots,7\}$ with lines \[ \{1,2,3\},\ \{1,4,5\},\ \{1,6,7\},\ \{2,4,6\},\ \{2,5,7\},\ \{3,4,7\},\ \{3,5,6\}. \] - $n=3$: the standard plane $\mathrm{PG}(2,3)$ with $13$ points and $13$ lines of size $4$ (constructed via $1$- and $2$-dimensional subspaces of $\mathbb F_3^3$).

In each case the script checked that every pair of distinct points lies in exactly one line.

Lemma 1 (design parameters forced by the axioms). Assume $(P,\mathcal L)$ satisfies (a)--(b). Then:

(i) Every point lies on exactly $n+1$ lines.

(ii) The number of lines is $|\mathcal L|=n^2+n+1$.

Proof. (i) Fix a point $x\in P$. Consider the set of unordered pairs $\{x,y\}$ with $y\in P\setminus\{x\}$. There are $|P|-1 = n^2+n$ such pairs.

Each line $L\in\mathcal L$ that contains $x$ contributes exactly $|L\setminus\{x\}|=n$ pairs of the form $\{x,y\}$ with $y\in L\setminus\{x\}$.

By axiom (b), every pair $\{x,y\}$ lies on exactly one line, so the pairs $\{x,y\}$ are partitioned by the lines through $x$. Therefore, \[ (\#\{L\in\mathcal L: x\in L\})\cdot n = n^2+n, \] so $\#\{L\in\mathcal L: x\in L\}=n+1$.

(ii) Count incidences $(x,L)$ with $x\in P$, $L\in\mathcal L$, $x\in L$ in two ways.

From (i), each of the $|P|=n^2+n+1$ points lies on $n+1$ lines, giving $|P|(n+1)$ incidences.

On the other hand, each of the $|\mathcal L|$ lines contains $n+1$ points, giving $|\mathcal L|(n+1)$ incidences.

Equating these gives $|\mathcal L|(n+1)=|P|(n+1)$, hence $|\mathcal L|=|P|=n^2+n+1$. $\square$

Lemma 2 (any two lines meet in exactly one point). Assume $(P,\mathcal L)$ satisfies (a)--(b). Then for any two distinct lines $L,M\in\mathcal L$ we have $|L\cap M|=1$.

Proof. First, $|L\cap M|\le 1$: if $L\cap M$ contained two distinct points $x\ne y$, then the pair $\{x,y\}$ would be contained in both $L$ and $M$, contradicting uniqueness in (b).

It remains to rule out $L\cap M=\emptyset$. Assume for contradiction that $L$ and $M$ are disjoint. Choose a point $p\in L$.

For each $q\in M$, let $N_q\in\mathcal L$ be the unique line containing $\{p,q\}$ (exists and is unique by (b)). We claim:

$1$ For each $q\in M$, $N_q\cap L = \{p\}$. Indeed, $p\in N_q\cap L$. If there were some $p'\in (N_q\cap L)\setminus\{p\}$, then the pair $\{p,p'\}$ would be contained in both $L$ and $N_q$, forcing $L=N_q$ by uniqueness in (b). But $N_q$ contains $q\in M$ while $L\cap M=\emptyset$, contradiction.

$2$ For each $q\in M$, $N_q\cap M = \{q\}$. Indeed, $q\in N_q\cap M$. If there were $q'\in (N_q\cap M)\setminus\{q\}$, then the pair $\{q,q'\}$ would be contained in both $M$ and $N_q$, contradicting uniqueness in (b).

$3$ If $q_1\ne q_2$ in $M$, then $N_{q_1}\cap N_{q_2}=\{p\}$. We already know $p\in N_{q_1}\cap N_{q_2}$. If there were another point $r\ne p$ in the intersection, then the pair $\{p,r\}$ would be contained in both $N_{q_1}$ and $N_{q_2}$, contradicting uniqueness in (b).

Now count the size of the union \[ U := M\ \cup\ \bigcup_{q\in M} (N_q\setminus\{p\}). \] By $2$, for each $q\in M$ the set $N_q\setminus\{p\}$ contains $q$ and $n-1$ other points (since $|N_q|=n+1$). By $3$, the sets $N_q\setminus\{p\}$ for different $q$ are disjoint. Therefore \[ |U| = |M| + \sum_{q\in M} |N_q\setminus\{p\}| = (n+1) + (n+1)\cdot n = n^2+n+1 = |P|. \] Hence $U=P$.

But by $1$ we have $L\cap (N_q\setminus\{p\})=\emptyset$ for all $q\in M$, and also $L\cap M=\emptyset$ by assumption. Thus $L\cap U = \{p\}$. So $L$ contains only one point of $U=P$, contradicting $|L|=n+1\ge 2$.

Therefore $L$ and $M$ cannot be disjoint, and since $|L\cap M|\le 1$ we must have $|L\cap M|=1$. $\square$

5) VERIFICATION

- Quantifiers: Lemmas 1--2 assume exactly the axioms given (a)--(b) and the exact ground set size $|P|=n^2+n+1$. - Boundary case $n=1$: Lemma 1 gives $n+1=2$ lines through each point, and $|\mathcal L|=3$, which matches the explicit example. Lemma 2 holds: any two $2$-subsets of a $3$-set intersect in exactly one point. - In Lemma 2, the disjointness of the sets $N_q\setminus\{p\}$ is checked via uniqueness of the pair $\{p,r\}$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Any structure satisfying the problem's definition is a symmetric $2$-$(n^2+n+1,\ n+1,\ 1)$ design: every point lies on exactly $n+1$ lines, the number of lines equals the number of points, and any two distinct lines intersect in exactly one point (Lemmas 1--2). Small cases $n=1,2,3$ exist and were computationally verified.

(ii) First gap (crisp): Prove or disprove: if such a $2$-$(n^2+n+1,\ n+1,\ 1)$ symmetric design exists, then $n$ is a prime power.

(iii) Top 3 next moves: 1. For the smallest open candidate $n=12$, search for additional necessary arithmetic constraints beyond those listed (e.g. incidence-matrix rank obstructions) and check them computationally. 2. Try to coordinatize the design: show that the algebra of "translations" or automorphisms forces a finite field of size $n$. 3. Develop a contradiction from prime factorization of $n$ using $p$-adic invariants of the incidence matrix (e.g. constraints on its determinant/eigenvalues).

(iv) Minimal counterexample structure: A counterexample would be a symmetric block design with parameters $v=b=n^2+n+1$ and block size $k=r=n+1$, with $\lambda=1$, where $n$ is not a prime power (the smallest candidate is $n=12$, i.e. $v=157$, $k=13$).

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT

Fix an integer $n\ge 1$. Let $P$ be a set of size \[ |P| = n^2+n+1. \] A finite projective plane of order $n$ (as defined in the problem statement) is a collection $\mathcal L$ of subsets of $P$ (called lines) such that:

(a) Every line has size $n+1$: for all $L\in\mathcal L$, $|L|=n+1$.

(b) Every unordered pair of distinct points lies on exactly one line: for all distinct $x,y\in P$, there exists a unique $L\in\mathcal L$ with $\{x,y\}\subseteq L$.

Question: If such $(P,\mathcal L)$ exists, must $n$ be a prime power (i.e. $n=p^m$ for some prime $p$ and integer $m\ge 1$)?

Edge cases/conventions: The definition makes sense for $n=1$ and gives a non-degenerate structure. We do not consider $n=0$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement itself records:

- Constructions exist whenever $n$ is a prime power. - The conjecture is verified for $n\le 11$. - It is open whether a projective plane of order $12$ exists. - (Bruck--Ryser) If $n\equiv 1\pmod 4$ or $n\equiv 2\pmod 4$, then $n$ must be a sum of two squares (e.g. this rules out $n=6,14$). - The case $n=10$ was ruled out by computer search.

I do not use any facts beyond what is explicitly stated above.

3) ATTACK PLAN

Proof track ideas (unlikely to close here): - Extract algebraic structure from incidences (coordinate the plane) and force a finite field of size $n$. - Use strong arithmetic constraints on incidence matrices (eigenvalues, $p$-ranks) to force prime-power order.

Disproof track ideas: - Try to construct an explicit incidence structure of order $n$ for a non-prime-power $n$ (smallest candidate is $n=12$).

Given the status, I focus on rigorous internal consequences of the given axioms and small-case verification.

4) WORK

FAST REALITY CHECK.

I verified by explicit construction (and a short script) that projective planes of order $n=1,2,3$ exist:

- $n=1$: $P=\{1,2,3\}$ and $\mathcal L=\{\{1,2\},\{1,3\},\{2,3\}\}$. - $n=2$: the Fano plane on $P=\{1,\dots,7\}$ with lines \[ \{1,2,3\},\ \{1,4,5\},\ \{1,6,7\},\ \{2,4,6\},\ \{2,5,7\},\ \{3,4,7\},\ \{3,5,6\}. \] - $n=3$: the standard plane $\mathrm{PG}(2,3)$ with $13$ points and $13$ lines of size $4$ (constructed via $1$- and $2$-dimensional subspaces of $\mathbb F_3^3$).

In each case the script checked that every pair of distinct points lies in exactly one line.

Lemma 1 (design parameters forced by the axioms). Assume $(P,\mathcal L)$ satisfies (a)--(b). Then:

(i) Every point lies on exactly $n+1$ lines.

(ii) The number of lines is $|\mathcal L|=n^2+n+1$.

Proof. (i) Fix a point $x\in P$. Consider the set of unordered pairs $\{x,y\}$ with $y\in P\setminus\{x\}$. There are $|P|-1 = n^2+n$ such pairs.

Each line $L\in\mathcal L$ that contains $x$ contributes exactly $|L\setminus\{x\}|=n$ pairs of the form $\{x,y\}$ with $y\in L\setminus\{x\}$.

By axiom (b), every pair $\{x,y\}$ lies on exactly one line, so the pairs $\{x,y\}$ are partitioned by the lines through $x$. Therefore, \[ (\#\{L\in\mathcal L: x\in L\})\cdot n = n^2+n, \] so $\#\{L\in\mathcal L: x\in L\}=n+1$.

(ii) Count incidences $(x,L)$ with $x\in P$, $L\in\mathcal L$, $x\in L$ in two ways.

From (i), each of the $|P|=n^2+n+1$ points lies on $n+1$ lines, giving $|P|(n+1)$ incidences.

On the other hand, each of the $|\mathcal L|$ lines contains $n+1$ points, giving $|\mathcal L|(n+1)$ incidences.

Equating these gives $|\mathcal L|(n+1)=|P|(n+1)$, hence $|\mathcal L|=|P|=n^2+n+1$. $\square$

Lemma 2 (any two lines meet in exactly one point). Assume $(P,\mathcal L)$ satisfies (a)--(b). Then for any two distinct lines $L,M\in\mathcal L$ we have $|L\cap M|=1$.

Proof. First, $|L\cap M|\le 1$: if $L\cap M$ contained two distinct points $x\ne y$, then the pair $\{x,y\}$ would be contained in both $L$ and $M$, contradicting uniqueness in (b).

It remains to rule out $L\cap M=\emptyset$. Assume for contradiction that $L$ and $M$ are disjoint. Choose a point $p\in L$.

For each $q\in M$, let $N_q\in\mathcal L$ be the unique line containing $\{p,q\}$ (exists and is unique by (b)). We claim:

$1$ For each $q\in M$, $N_q\cap L = \{p\}$. Indeed, $p\in N_q\cap L$. If there were some $p'\in (N_q\cap L)\setminus\{p\}$, then the pair $\{p,p'\}$ would be contained in both $L$ and $N_q$, forcing $L=N_q$ by uniqueness in (b). But $N_q$ contains $q\in M$ while $L\cap M=\emptyset$, contradiction.

$2$ For each $q\in M$, $N_q\cap M = \{q\}$. Indeed, $q\in N_q\cap M$. If there were $q'\in (N_q\cap M)\setminus\{q\}$, then the pair $\{q,q'\}$ would be contained in both $M$ and $N_q$, contradicting uniqueness in (b).

$3$ If $q_1\ne q_2$ in $M$, then $N_{q_1}\cap N_{q_2}=\{p\}$. We already know $p\in N_{q_1}\cap N_{q_2}$. If there were another point $r\ne p$ in the intersection, then the pair $\{p,r\}$ would be contained in both $N_{q_1}$ and $N_{q_2}$, contradicting uniqueness in (b).

Now count the size of the union \[ U := M\ \cup\ \bigcup_{q\in M} (N_q\setminus\{p\}). \] By $2$, for each $q\in M$ the set $N_q\setminus\{p\}$ contains $q$ and $n-1$ other points (since $|N_q|=n+1$). By $3$, the sets $N_q\setminus\{p\}$ for different $q$ are disjoint. Therefore \[ |U| = |M| + \sum_{q\in M} |N_q\setminus\{p\}| = (n+1) + (n+1)\cdot n = n^2+n+1 = |P|. \] Hence $U=P$.

But by $1$ we have $L\cap (N_q\setminus\{p\})=\emptyset$ for all $q\in M$, and also $L\cap M=\emptyset$ by assumption. Thus $L\cap U = \{p\}$. So $L$ contains only one point of $U=P$, contradicting $|L|=n+1\ge 2$.

Therefore $L$ and $M$ cannot be disjoint, and since $|L\cap M|\le 1$ we must have $|L\cap M|=1$. $\square$

5) VERIFICATION

- Quantifiers: Lemmas 1--2 assume exactly the axioms given (a)--(b) and the exact ground set size $|P|=n^2+n+1$. - Boundary case $n=1$: Lemma 1 gives $n+1=2$ lines through each point, and $|\mathcal L|=3$, which matches the explicit example. Lemma 2 holds: any two $2$-subsets of a $3$-set intersect in exactly one point. - In Lemma 2, the disjointness of the sets $N_q\setminus\{p\}$ is checked via uniqueness of the pair $\{p,r\}$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Any structure satisfying the problem's definition is a symmetric $2$-$(n^2+n+1,\ n+1,\ 1)$ design: every point lies on exactly $n+1$ lines, the number of lines equals the number of points, and any two distinct lines intersect in exactly one point (Lemmas 1--2). Small cases $n=1,2,3$ exist and were computationally verified.

(ii) First gap (crisp): Prove or disprove: if such a $2$-$(n^2+n+1,\ n+1,\ 1)$ symmetric design exists, then $n$ is a prime power.

(iii) Top 3 next moves: 1. For the smallest open candidate $n=12$, search for additional necessary arithmetic constraints beyond those listed (e.g. incidence-matrix rank obstructions) and check them computationally. 2. Try to coordinatize the design: show that the algebra of "translations" or automorphisms forces a finite field of size $n$. 3. Develop a contradiction from prime factorization of $n$ using $p$-adic invariants of the incidence matrix (e.g. constraints on its determinant/eigenvalues).

(iv) Minimal counterexample structure: A counterexample would be a symmetric block design with parameters $v=b=n^2+n+1$ and block size $k=r=n+1$, with $\lambda=1$, where $n$ is not a prime power (the smallest candidate is $n=12$, i.e. $v=157$, $k=13$).