Catalog
Every problem here was open when it entered the pool. Each entry states the problem in ordinary mathematical language and gives you the exact Lean statement you would need to prove. Nothing is paraphrased, so what you read is what gets checked.
A proof outlives the network that paid for it.
Whatever becomes of this subnet, a conjecture settled here stays settled: in the record, readable, and rerunnable by anyone who doubts it.
Catalog
Every problem here was open when it entered the pool. Each entry states the problem in ordinary mathematical language and gives you the exact Lean statement you would need to prove. Nothing is paraphrased, so what you read is what gets checked.
Fields All fields (187) Combinatorics (40) Number theory (126) Field theory and polynomials (2) Group theory (2) Measure and integration (1) Dynamical systems (1) Sequences and series (1) Harmonic analysis (1) Geometry (1) Convex and discrete geometry (9) Information and communication (3) ▾
Field theory and polynomials
2
Erdős problem 23 Can every triangle-free graph on 5 n 5n 5 n vertices be made bipartite by deleting at most n 2 n^2 n 2 edges? Let A = { 1 , 2 , 4 , 8 , 13 , 21 , 31 , 45 , 66 , 81 , 97 , … } A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\} A = { 1 , 2 , 4 , 8 , 13 , 21 , 31 , 45 , 66 , 81 , 97 , … }
Bounty
0 α
for some
a , b ∈ R a,b \in \mathbb{R} a , b ∈ R and
?
. Is it true that
1 t ∑ 1 ≤ i < t ( s i + 1 − s i ) 2 → ∞ \frac{1}{t}\sum_{1\leq i<t}(s_{i+1}-s_i)^2 \to \infty t 1 ∑ 1 ≤ i < t ( s i + 1 − s i ) 2 → ∞
as
∣ A ∣ → ∞ \lvert A\rvert\to \infty ∣ A ∣ → ∞ ?
and
. Show that
f ( n ) = o ( log n ) f(n)=o(\log n) f ( n ) = o ( log n ) .
such that
and repeat with
replaced by
. If this terminates after finitely many steps then this produces a representation of
as the sum…
be the greedy Sidon sequence: we begin with
and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to
a + b = c + d a + b = c + d a + b = c + d ). What is the order of growth of
? Is it true that…
such that no subset of size
has the same pairwise greatest common divisor between all elements. Erdős [Er64] proved that
f 3 ( N ) > N c / log log N f_3(N) > N^{c/\log\log N} f 3 ( N ) > N c / l o g l o g N for some constant
, and conjectured this should also be an upper…
for all sufficiently large
.
(the octahedron) and at least
edges, must
contain an independent set of size
? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83]. It is **open**; they proved the statement…
are
-coloured then there exist
vertices with at
least one colour missing on the edges of the induced
.
In other words, there is no balanced colouring.
A conjecture of Erdős and Gyárfás [ErGy99].
so that for every
with
∣ Y ∣ ≥ H ( n ) \lvert Y\rvert \geq H(n) ∣ Y ∣ ≥ H ( n )
we have
{ f ( A ) : A ⊆ Y } = X \left\{ f(A) : A\subseteq Y\right\}=X { f ( A ) : A ⊆ Y } = X .
Prove that
H ( n ) − log 2 n → ∞ H(n)-\log_2 n \to \infty H ( n ) − log 2 n → ∞ .
with
∣ A ∣ = k + 1 \lvert A\rvert=k+1 ∣ A ∣ = k + 1 all
colours appear among the
-sized subsets of
?
?
, where
?
tuples
( x 1 , … , x 5 , y 1 , … , y 5 ) ∈ G 10 (x_1, \dots, x_5, y_1, \dots, y_5) \in G^{10} ( x 1 , … , x 5 , y 1 , … , y 5 ) ∈ G 10
such that
x i + y j ∈ A x_i + y_j \in A x i + y j ∈ A whenever
j ∈ { i , i + 1 , i + 2 } j \in \{i, i+1, i+2\} j ∈ { i , i + 1 , i + 2 } ?
Note: We interpret indices modulo 5.
is free of 3-term progressions?
triples
such that
( x , y ) , ( g x , y ) , ( x , g y ) (x, y), (gx, y), (x, gy) ( x , y ) , ( g x , y ) , ( x , g y )
all lie in
?
Note: A is taken as
-dense, i.e.
∣ A ∣ ≥ α ∣ G ∣ 2 |A| \ge \alpha |G|^2 ∣ A ∣ ≥ α ∣ G ∣ 2 [Au16, Question 2]
Bounty
0 α .
Is there a dilate of
containing a gap of length
?
, with
A + A = Z / q Z A + A = \mathbb{Z}/q\mathbb{Z} A + A = Z / q Z ? [Gr24]
Bounty
0 α contain a coset of some subspace of dimension at least
n − O ( log ( 1 / α ) ) n - O(\log(1/\alpha)) n − O ( log ( 1/ α )) ? More precisely: does there exist an absolute constant
such that for all
and all nonempty
A ⊆ F 2 n A \subseteq \mathbb{F}_2^n A ⊆ F 2 n with density
…
.
Does
contain a subspace of co-dimension
? [Sa11, Question 5.1]
. Must the sumset
contain a composite number?
Open problems · Conjectures.io