The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 29 of 280 problems in Discrete geometry

NT-LATTICE-027

Gauss Circle-Problem Exponent Conjecture

MajorExact constant problemc. 1915

For

R \geq 1

, let

P (R) = # {(m, n) \in Z^{2} : m^{2} + n^{2} \leq R^{2}} - π R^{2} .

Then for every

ε > 0

P (R) = O_{ε} (R^{1/2 + ε}) (R \to \infty) .

ANAL-FA-006

Kakeya set conjecture in dimensions $n\ge4$

LandmarkConjecturec. 1971

Let

n \geq 4

and let

E \subset R^{n}

be a Borel set such that for every

v \in S^{n - 1}

there is

x_{v} \in R^{n}

with

{x_{v} + t v : 0 \leq t \leq 1} \subset E

. Then

dim_{H} E = n

ANAL-FA-014

Two-dimensional Fuglede conjecture

MajorCanonical finite case1974

Let

Ω \subset R^{2}

be a bounded Lebesgue measurable set of positive measure. The following are equivalent: (i) there is a countable

Λ \subset R^{2}

such that

{∣Ω ∣^{- 1/2} e^{2 πiλ \cdot x} : λ \in Λ}

is an orthonormal basis of

L^{2} (Ω)

; (ii) there is a countable

T \subset R^{2}

such that

\sum_{t \in T} 1_{Ω} (x - t) = 1

for almost every

x \in R^{2}

COMB-001

Erdős–Szekeres Convex Polygon Conjecture

LandmarkConjecture1935

For

k \geq 3

, let

f (k)

be the least integer

N

such that every

N

-point set in the plane with no three collinear contains

k

points that are the vertices of their convex hull. Then

f (k) = 2^{k - 2} + 1.

COMB-006

Ryser–Brualdi–Stein Latin Transversal Conjecture

MajorConjecture1967–1975

Let

L

be a Latin square of order

n

, meaning an

n \times n

array on

n

symbols in which every symbol occurs once in every row and every column. A partial transversal is a set of cells using no row, column, or symbol twice. Then:

every L has a partial transversal of size n - 1,

and, if

n

is odd, every

L

has a transversal of size

n

COMB-012

Existence of a Finite Projective Plane of Order $12$

MajorCanonical finite caseUnknown

Do there exist sets

P

(points) and

L

(lines), each of size

1 2^{2} + 12 + 1 = 157

, and an incidence relation

I \subseteq P \times L

, such that every line is incident with exactly

13

points, every point is incident with exactly

13

lines, every two distinct points lie on exactly one common line, and every two distinct lines meet in exactly one point?

DG-001

Erdős Distinct-Distances Conjecture

LandmarkConjecture1946

Let

g (n) = P \subset R^{2} ∣ P ∣ = n min {∥ x - y ∥_{2} : x, y \in P, x \neq = y} .

There is an absolute constant

c > 0

such that, for all

n \geq 2

g (n) \geq c \frac{n}{lo g n} .

DG-004

Falconer's Distance Set Conjecture

LandmarkConjecture1985

Let

d \geq 2

and let

E \subset R^{d}

be compact. Write

dim_{H}

for Hausdorff dimension. If

dim_{H} (E) > \frac{d}{2},

then its distance set

Δ (E) = {∥ x - y ∥_{2} : x, y \in E}

has positive one-dimensional Lebesgue measure.

DG-006

Hadwiger–Levi Illumination Conjecture

LandmarkConjecture1957–1960

Let

d \geq 2

, let

S^{d - 1}

be the unit sphere, and let

K \subset R^{d}

be a convex body. Say that a direction

u \in S^{d - 1}

illuminates

x \in \partial K

x + t u \in int K

for some

t > 0

. There exist at most

2^{d}

directions such that every point of

\partial K

is illuminated by at least one of them.

DG-007

Mahler Volume-Product Conjecture

LandmarkConjecture1939

For a convex body

K \subset R^{d}

containing

0

in its interior, put

K^{\circ} = {y : ⟨ x, y ⟩ \leq 1 \forall x \in K}

. If

K = - K

, then

vol (K) vol (K^{\circ}) \geq \frac{4 ^{d}}{d !} .

For arbitrary

K

, let

s (K)

be its Santaló point, the minimizer of

vol ((K - x)^{\circ})

over

x \in int K

. Then

vol (K) vol ((K - s (K))^{\circ}) \geq \frac{( d + 1 ) ^{d + 1}}{( d ! ) ^{2}} .

DG-009

Toeplitz Square-Peg Conjecture

LandmarkConjecture1911

For every continuous injective map

γ : S^{1} \to R^{2}

, the Jordan curve

γ (S^{1})

contains four distinct points that are the vertices of a nondegenerate Euclidean square.

DG-017

High-Dimensional Sphere-Packing Exponent

LandmarkOpen problemc. 1900

Let

Δ_{d}

be the supremal density of a packing of congruent balls in

R^{d}

. Determine the exponential asymptotics of

Δ_{d}

, equivalently determine

d \to \infty lim inf \frac{1}{d} lo g_{2} Δ_{d} and d \to \infty lim sup \frac{1}{d} lo g_{2} Δ_{d},

and decide whether these two quantities are equal.

DG-003

Exact Growth of the Planar Unit-Distance Function

MajorOpen problem1946

For

n \geq 2

, set

u (n) = P \subset R^{2} ∣ P ∣ = n max {{x, y} \subset P : ∥ x - y ∥_{2} = 1}

and

α_{U} = n \to \infty lim sup \frac{lo g u ( n )}{lo g n} .

Determine the exact value of

α_{U}

(and, more finely, the asymptotic order of

u (n)

DG-005

Erdős–Ulam Rational-Distance Problem

MajorOpen problem1946

Does there exist a countable dense set

S \subset R^{2}

such that

∥ x - y ∥_{2} \in Q for every x, y \in S ?

DG-010

Reinhardt's Smoothed-Octagon Conjecture

MajorConjecture1934

For a centrally symmetric convex disk

K \subset R^{2}

, define

δ_{L} (K) = Λ sup \frac{area ( K )}{det Λ},

where the supremum is over full-rank lattices

Λ \subset R^{2}

for which the interiors of the translates

K + λ

λ \in Λ

, are pairwise disjoint. Let

O

be Reinhardt's smoothed octagon, obtained from a regular octagon by replacing each vertex by the hyperbola arc tangent to its two incident sides and asymptotic to the two adjacent nonincident sides. Then

δ_{L} (K) \geq δ_{L} (O) = \frac{8 - 4 2 - lo g 2}{2 2 - 1} .

DG-011

Kalai's $3^d$ Conjecture

MajorConjecture1989

Every centrally symmetric convex

d

-polytope has at least

3^{d}

nonempty faces in total, counting faces of every dimension

0, \dots, d

and counting the polytope itself.

DG-012

Five-Dimensional Kissing Number

MajorExact constant problemUnknown

Let

S^{4} = {x \in R^{5} : ∥ x ∥_{2} = 1}

. Determine

τ_{5} = max {∣ X ∣ : X \subset S^{4}, ⟨ x, y ⟩ \leq \frac{1}{2} for all distinct x, y \in X} .

Equivalently,

τ_{5}

is the maximum number of nonoverlapping unit

5

-balls that can simultaneously touch a fixed unit

5

-ball.

DG-013

Optimal Sphere Packing in Dimension Five

MajorConjecturec. 1900

For a packing

P

of congruent closed balls in

R^{5}

with disjoint interiors, define its upper asymptotic density by

\overline{ρ} (P) = R \to \infty lim sup x \in R^{5} sup \frac{vol _{5} ( B ( x , R ) \cap ⋃ _{B \in P} B )}{vol _{5} ( B ( x , R ))},

where

B (x, R)

is the radius-

R

ball centered at

x

. Let

Δ_{5}

be the supremum of

\overline{ρ} (P)

over all such packings. Then

Δ_{5} = \frac{π ^{2}}{15 2},

the density attained by the

D_{5}

root-lattice packing.

DG-014

Four-Dimensional Borsuk Problem

MajorCanonical finite case1933

Let

b (4)

be the least

m

such that every bounded set

S \subset R^{4}

of positive diameter can be partitioned into

m

subsets, each having diameter strictly smaller than

diam (S)

. Is

b (4) = 5 ?

DG-015

Lebesgue's Universal Covering Problem

MajorExact constant problem1914

Let

U = in f {area (K) : K \subset R^{2} is convex and every planar set S with diam (S) \leq 1 has an isometric copy contained in K} .

Determine the exact value of

U

, and whether the infimum is attained.

DG-019

Ehrhart Volume Conjecture

MajorConjecture1964

Let

K \subset R^{n}

be a convex body whose barycenter is the origin and whose only interior lattice point is

0

. Then

vol (K) \leq \frac{( n + 1 ) ^{n}}{n !} .

Moreover, equality holds only for unimodular images of the centered simplex

(n + 1) conv (0, e_{1}, \dots, e_{n}) - (1, \dots, 1) .

OPT-003

Polynomial Hirsch conjecture

MajorConjecturec. 1992

There is a polynomial

p \in R [X, Y]

such that, for all integers

d \geq 1

n \geq d + 1

, and every

d

-dimensional convex polytope

P

having exactly

n

facets, the graph whose vertices and edges are the

0

- and

1

-dimensional faces of

P

has diameter at most

p (n, d)

TCS-030

Fixed-Polynomial-Factor Hardness of Euclidean Closest Vector

MajorConjecturec. 2003

There exists a constant

ε > 0

for which the following promise problem is

NP

-hard under deterministic polynomial-time many-one reductions: given a lattice basis

B \in Z^{m \times n}

, target

t \in Z^{m}

, and radius

r > 0

, distinguish

dist_{2} (t, L (B)) \leq r from dist_{2} (t, L (B)) > n^{ε} r .

INFO-005

Asymptotic Spherical-Code Rate

MajorOpen problem1959

For

- 1 < s < 1

, let

A_{S} (d, s)

be the largest number of unit vectors in

R^{d}

whose pairwise inner products are at most

s

. Determine the asymptotic rate

R_{S} (s) = d \to \infty lim sup \frac{1}{d} lo g_{2} A_{S} (d, s)

for every fixed

s

, and determine where the corresponding limit exists.

MATH-PHYS-005

Three-dimensional Coulomb crystallization

MajorConjecturec. 1934

Let

Λ_{L} = (R / L Z)^{3}

, let

N = L^{3} \in N

, and let

G_{L}

be the zero-mean periodic Coulomb Green function satisfying

- Δ G_{L} = 4 π (δ_{0} - L^{- 3})

. For pairwise distinct

x_{1}, \dots, x_{N} \in Λ_{L}

, define the neutral-jellium energy, with the point self-energies omitted, by

E_{L} (x_{1}, \dots, x_{N}) = 1 \leq i < j \leq N \sum G_{L} (x_{i} - x_{j}) - i = 1 \sum N \int_{Λ_{L}} G_{L} (x_{i} - y) d y + \frac{1}{2} \iint_{Λ_{L}^{2}} G_{L} (x - y) d x d y .

Then

L \to \infty L^{3} \in N lim L^{- 3} x_{1}, \dots, x_{L^{3}} \in Λ_{L} x_{i} \neq = x_{j} (i \neq = j) in f E_{L} (x_{1}, \dots, x_{L^{3}}) = e_{BCC},

where

e_{BCC}

is the thermodynamic energy per unit volume of the unit-density body-centered-cubic lattice under the same normalization.