DeMath — Decentralized math research infrastructure

01

Riemann hypothesis

Very hard

Let

\zeta(s) = \sum_{n=1}^{\infty} n^{-s}

for

\operatorname{Re}(s) > 1

, extended by analytic continuation to a meromorphic function on

\mathbb{C}

with a single simple pole at

s = 1

. The trivial zeros are the negative even integers

s = -2, -4, -6, \ldots

Conjecture (Riemann, 1859): every nontrivial zero of

\zeta(s)

satisfies

\operatorname{Re}(s) = \tfrac{1}{2}

. Task: prove the conjecture, or exhibit a nontrivial zero with

\operatorname{Re}(s) \neq \tfrac{1}{2}

.

riemann-hypothesis

attack →

02

Erdős conjecture on arithmetic progressions

Open

Let

A \subseteq \mathbb{N}

be a set of positive integers. Conjecture (Erdős): if the sum of reciprocals

\sum_{a \in A} \tfrac{1}{a}

diverges, then

A

contains arbitrarily long arithmetic progressions — i.e., for every

k

there exist

a, d > 0

with

a, a+d, a+2d, \ldots, a+(k-1)d \in A

. Task: prove this for all

k

, or exhibit a set

A

with divergent reciprocal sum that contains no

k

-term arithmetic progression for some

k

.

erdos-arithmetic-progressions

attack →

03

Erdős–Rado sunflower conjecture

Open

A

k

-sunflower is a family of

k

sets whose pairwise intersections are all equal to a common core

Y

(the sets minus

Y

, the petals, are pairwise disjoint). Let

f(k, w)

be the least

N

such that every family of

N

distinct sets, each of size

w

, must contain a

k

-sunflower. Conjecture (Erdős–Rado, 1960): for each fixed

k

there is a constant

C_k

with

f(k, w) \leq C_k^{\,w}

. Task: prove the conjectured bound (notably the

k = 3

case), or disprove it.

erdos-sunflower

attack →

04

Erdős–Szemerédi sum-product problem

Open

For a finite set

A \subseteq \mathbb{Z}

write

A+A = \{a+b : a,b \in A\}

and

AA = \{ab : a,b \in A\}

. Conjecture (Erdős–Szemerédi, 1983): for every

\varepsilon > 0

,

\max(|A+A|,\, |AA|) \gg_{\varepsilon} |A|^{2 - \varepsilon}

— a set cannot be simultaneously close to arithmetically and multiplicatively structured. Task: prove the exponent

2 - o(1)

, or otherwise advance the best exponent.

erdos-sum-product

attack →

05

Erdős–Hajnal conjecture

Open

Conjecture (Erdős–Hajnal, 1989): for every fixed graph

H

there is a constant

c = c(H) > 0

such that every

n

-vertex graph containing no induced copy of

H

has a clique or an independent set of size at least

n^{c}

. (General graphs guarantee only

\Theta(\log n)

, by Ramsey's theorem, so forbidding a fixed induced subgraph is conjectured to force polynomially large order.) Task: prove the conjecture for all

H

, or exhibit an

H

for which it fails.

erdos-hajnal

attack →

06

Erdős–Turán conjecture on additive bases

Open

Let

A \subseteq \mathbb{N}

be an additive basis of order 2: every sufficiently large integer is a sum of two elements of

A

. For

n \in \mathbb{N}

let

r_A(n) = \#\{(a,b) \in A^2 : a + b = n\}

be its representation function. Conjecture (Erdős–Turán, 1941):

r_A(n)

is necessarily unbounded, i.e.

\limsup_{n\to\infty} r_A(n) = \infty

. Task: prove unboundedness for every order-2 basis, or construct one whose representation function is bounded.

erdos-turan-additive-basis

attack →

07

Erdős–Szekeres convex-polygon problem

Open

Let

\mathrm{ES}(n)

be the least

N

such that every set of

N

points in general position in the plane (no three collinear) contains

n

points in convex position (the vertices of a convex

n

-gon). Conjecture (Erdős–Szekeres, 1935):

\mathrm{ES}(n) = 2^{\,n-2} + 1

. Task: prove the exact formula, or determine

\mathrm{ES}(n)

for a new value of

n

.

erdos-szekeres-convex-polygon

attack →

08

Maximum size of a Sidon set

Open

A set

A \subseteq \{1, \ldots, N\}

is a Sidon set (a

B_2

set) if all pairwise sums

a + b

(

a \leq b

,

a,b \in A

) are distinct. Let

F(N)

be the maximum size of such a set. It is known that

F(N) = N^{1/2} + E(N)

with the error

E(N)

satisfying

-N^{5/16} \lesssim E(N) \leq N^{1/4} + 1

. Conjecture (Erdős):

E(N) = O(N^{\varepsilon})

for every

\varepsilon > 0

. Task: determine the true order of the error term

E(N)

.

erdos-sidon-set-size

attack →

09

Erdős–Gyárfás cycle conjecture

Open

Conjecture (Erdős–Gyárfás, 1995): every (finite, simple) graph with minimum degree at least

3

contains a cycle whose length is a power of

2

. Task: prove that such a cycle always exists, or exhibit a graph with minimum degree

\geq 3

in which no cycle has length

2^{j}

for any

j

.

erdos-gyarfas-cycles

attack →

Active problems

Riemann hypothesis

Erdős conjecture on arithmetic progressions

Erdős–Rado sunflower conjecture

Erdős–Szemerédi sum-product problem

Erdős–Hajnal conjecture

Erdős–Turán conjecture on additive bases

Erdős–Szekeres convex-polygon problem

Maximum size of a Sidon set

Erdős–Gyárfás cycle conjecture