Vela Mathematics Program: problems

Narrowed tosource:erdos-ai-contributions-wiki ×Clear all

Problem ledger

353 problems · 6/8Number SourcesGraph view

declared disproved (Lean) · formalizederdos:897

False ↔ ∀ (f : ℕ → ℝ), (∀ a > 0, ∀ b > 0, a.Coprime b → f (a * b) = f a + f b) → Filter.limsup (fun x => match x with | (p, k) => ↑(f (p ^ k)) / ↑(Real.log (↑p ^ k))) (Filter.atTop ⊓ Filter.principal {(p, k) | Nat.Prime p}) = ⊤ → Filter.limsup (fun n => (↑(f (n + 1)) - ↑(f n)) / ↑(Real.log ↑n)) Filter.atTop = ⊤

number theoryN/A6 sources

declared proved (Lean) · formalizederdos:898

∀ (A B C P L M N : EuclideanSpace ℝ (Fin 2)), AffineIndependent ℝ ![A, B, C] → P ∈ interior ((convexHull ℝ) {A, B, C}) → N ∈ affineSpan ℝ {A, B} → (affineSpan ℝ {P, N}).direction ⟂ (affineSpan ℝ {A, B}).direction → M ∈ affineSpan ℝ {B, C} → (affineSpan ℝ {P, M}).direction ⟂ (affineSpan ℝ {B, C}).direction → L ∈ affineSpan ℝ {C, A} → (affineSpan ℝ {P, L}).direction ⟂ (affineSpan ℝ {C, A}).direction → dist P A + dist P B + dist P C ≥ 2 * (dist P M + dist P N + dist P L)

geometryN/A5 sources

declared proved (Lean) · formalizederdos:904

True ↔ ∀ (V : Type u_1) [inst : Fintype V] (G : SimpleGraph V) [inst_1 : DecidableRel G.Adj], ∀ r ∈ Set.Icc 1 (Erdos904.n V), Erdos904.turanNumber (Erdos904.n V) r ≤ G.edgeFinset.card → ∃ s, G.IsNClique r s ∧ 2 * r * G.edgeFinset.card ≤ Erdos904.n V * ∑ v ∈ s, G.degree v

graph theoryN/A5 sources

declared proved (Lean) · formalizederdos:905

∀ (n : ℕ) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj], ↑n ^ 2 / 4 < ↑G.edgeFinset.card → ∃ e ∈ G.edgeFinset, ↑n / 6 ≤ ↑(G.trianglesContaining e).card

graph theoryN/A5 sources

declared open · formalizederdos:906

Is there an entire non-zero function

f:\mathbb{C}\to \mathbb{C}

such that, for any infinite sequence

n_1<n_2<\cdots

, the set

\{ z: f^{(n_k)}(z)=0 \textrm{ for some }k\geq 1\}

is everywhere dense? The literal question is trivial for polynomials, so the claims address the transcendental entire case, in the affirmative.

analysisiterated functionsN/A5 sources

declared proved (Lean) · formalizederdos:907

True ↔ ∀ (f : ℝ → ℝ), (∀ (h : ℝ), 0 < h → Continuous fun x => f (x + h) - f x) → ∃ g a, Continuous g ∧ (∀ (x y : ℝ), a (x + y) = a x + a y) ∧ f = g + a

analysisN/A5 sources

declared proved (Lean) · formalizederdos:914

∀ {r m : ℕ}, 2 ≤ r → 1 ≤ m → ∀ {V : Type u_1} [inst : Fintype V] (G : SimpleGraph V) [inst_1 : DecidableRel G.Adj], Fintype.card V = r * m → m * (r - 1) ≤ G.minDegree → ∃ K, (∀ (i : Fin m), G.IsNClique r (K i)) ∧ Pairwise fun i j => Disjoint (K i) (K j)

graph theoryN/A5 sources

declared proved (Lean) · formalizederdos:923

True ↔ ∀ (V : Type u_1) (n : ℕ), ∃ k, ∀ (G : SimpleGraph V), ↑k ≤ G.chromaticNumber → ∃ H ≤ G, ↑n ≤ H.chromaticNumber ∧ H.CliqueFree 3

graph theorychromatic numberN/A5 sources

declared disproved (Lean)erdos:927

Erdős problem 927

graph theorypossible3 sources

declared open · formalizederdos:931

sorry ↔ ∀ (k₁ k₂ : ℕ), k₂ ≥ 3 → k₂ ≤ k₁ → {(n₁, n₂) | n₁ + k₁ ≤ n₂ ∧ (∏ i ∈ Finset.Icc 1 k₁, (n₁ + i)).primeFactors = (∏ j ∈ Finset.Icc 1 k₂, (n₂ + j)).primeFactors}.Finite

number theoryN/A3 sources

declared openerdos:935

Erdős problem 935

number theoryA057521 · A389244 · possible2 sources

declared open · formalizederdos:942

Let

h(n)

count powerful integers in

[n^2, (n+1)^2)

. What is the extremal order of

h(n)

number theorypossible4 sources

declared open · formalizederdos:943

True ↔ ∃ o, o =o[Filter.atTop] 1 ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ↑(AdditiveCombinatorics.sumRep Nat.Powerful n) ≤ ↑n ^ o n

number theorypossible4 sources

declared proved (Lean)erdos:947

Erdős problem 947

number theorycovering systemsN/A4 sources

declared solvederdos:948

Erdős problem 948

number theoryramsey theoryN/A3 sources

declared open · formalizederdos:949

True ↔ ∀ (S : Set ℝ), (∀ a ∈ S, ∀ b ∈ S, a + b ∉ S) → ∃ A ⊆ Sᶜ, Cardinal.mk ↑A = Cardinal.continuum ∧ A + A ⊆ Sᶜ

ramsey theoryN/A3 sources

declared open · formalizederdos:951

sorry ↔ ∀ (a : ℕ → ℝ), 1 < a 0 → StrictMono a → Erdos951.Erdos951Prop a → ∀ᶠ (x : ℝ) in Filter.atTop, {i | a i ≤ x}.ncard ≤ ⌊x⌋₊.primeCounting

number theoryN/A3 sources

declared openerdos:953

What is the largest possible measure of a subset of a radius-

R

disk in

\mathbb{R}^2

containing no pair of points at a positive integer distance? A Poisson-Bessel kernel argument gives

M(R) \ll R^{1/2}

; with Sárközy's lower construction,

M(R) = R^{1/2 + o(1)}

geometrydistancesN/A3 sources

declared openerdos:956

Erdős problem 956

geometrydistancesconvexpossible2 sources

declared disproved (Lean) · formalizederdos:958

False ↔ ∀ (n : ℕ) (A : Finset (EuclideanSpace ℝ (Fin 2))), A.card = n → (EuclideanGeometry.distanceSet A).card = n - 1 ∧ Finset.image (EuclideanGeometry.distanceMultiplicity A) (EuclideanGeometry.distanceSet A) = Finset.Icc 1 (n - 1) → Erdos958.IsEquidistantOnLine A ∨ Erdos958.IsEquidistantOnCircle A

distancesgeometryN/A5 sources

declared disprovederdos:960

Erdős problem 960

geometrypossible3 sources

declared openerdos:963

Erdős problem 963

number theorypossible2 sources

declared proved (Lean)erdos:964

Erdős problem 964

number theorydivisorsN/A4 sources

declared proved (Lean) · formalizederdos:966

Let

k,r\geq 2

. Does there exist a set

A\subseteq \mathbb{N}

that contains no non-trivial arithmetic progression of length

k+1

, yet in any

r

-colouring of

A

there must exist a monochromatic non-trivial arithmetic progression of length

k

? Answered in the affirmative.

number theoryadditive combinatoricsramsey theoryN/A6 sources

declared disproved (Lean) · formalizederdos:967

False ↔ ∀ (a : ℕ → ℕ), StrictMono a → 1 < a 0 → (Summable fun k => 1 / ↑(a k)) → ∀ (t : ℝ), 1 + ∑' (k : ℕ), Erdos967.summand t (a k) ≠ 0

number theoryanalysisN/A5 sources

declared proved (Lean) · formalizederdos:974

∀ {n : ℕ} [inst : NeZero n] (z : Fin n → ℂ), z 0 = 1 → {k | ∀ j < n - 1, ∑ i, z i ^ (k + j) = 0}.Infinite → Erdos974.IsTuranConfiguration z

analysisN/A5 sources

declared openerdos:976

Erdős problem 976

number theoryN/A2 sources

declared openerdos:983

Erdős problem 983

number theorypossible2 sources

declared provederdos:986

Erdős problem 986

graph theoryramsey theoryA000791 · A0594423 sources

declared proved · formalizederdos:987

True ↔ ∀ (x : ℕ → ℝ), (∀ (j : ℕ), x j ∈ Set.Ioo 0 1) → Filter.limsup (fun k => Erdos987.A x k) Filter.atTop = ⊤

analysisdiscrepancyN/A4 sources

declared disproved (Lean) · formalizederdos:990

False ↔ ∃ C, ∀ (f : Polynomial ℂ), f.coeff 0 ≠ 0 → ∀ (α β : ℝ), 0 ≤ α → α ≤ β → β ≤ 2 * Real.pi → |↑(Erdos990.rootArgCount f (Set.Icc α β)) - (β - α) / (2 * Real.pi) * ↑f.natDegree| ≤ C * √(↑f.support.card * Real.log (Erdos990.M f))

analysisN/A6 sources

declared openerdos:995

Erdős problem 995

analysisdiscrepancyN/A2 sources

declared open · formalizederdos:996

Let

n_1<n_2<\cdots

be a lacunary sequence of integers and

f\in L^2([0,1])

with

n

th Fourier partial sum

f_n

. Is there an absolute constant

C>0

such that if

\| f-f_n\|_2 \ll (\log\log\log n)^{-C}

then

\frac{1}{N}\sum_{k\leq N}f(\{\alpha n_k\})\to\int_0^1 f

for almost every

\alpha

? A preprint answers this negatively via a dyadic spike-block counterexample.

analysisN/A4 sources

declared proved (Lean) · formalizederdos:997

True ↔ ∀ (α : ℝ), ¬Erdos997.IsWellDistributed fun n => Int.fract (α * ↑(Nat.nth Nat.Prime n))

analysisdiscrepancyprimesN/A6 sources

declared proved (Lean) · formalizederdos:1000

True ↔ ∃ n, StrictMono n ∧ 0 < n 0 ∧ Filter.Tendsto (Erdos1000.phiAvg n) Filter.atTop (nhds 0)

number theorydiophantine approximationN/A5 sources

declared open · formalizederdos:1004

True ↔ ∀ c > 0, ∀ᶠ (x : ℕ) in Filter.atTop, ∃ n ≤ x, Erdos1004.IsDistinctTotientRun n ⌊Real.log ↑x ^ c⌋₊

number theorypossible3 sources

declared solved (Lean) · formalizederdos:1007

IsLeast {m | ∃ n G, G.HasDimension 4 ∧ G.edgeSet.ncard = m} sorry

graph theoryN/A5 sources

declared proved (Lean) · formalizederdos:1008

True ↔ ∃ c > 0, ∀ (V : Type) [Fintype V] (G : SimpleGraph V), ∃ H ≤ G, (SimpleGraph.cycleGraph 4).Free H ∧ c * ↑G.edgeSet.ncard ^ (2 / 3) ≤ ↑H.edgeSet.ncard

graph theoryN/A5 sources

declared proved (Lean) · formalizederdos:1014

∀ (k : ℕ), 3 ≤ k → Filter.Tendsto (fun l => ↑R(k, l + 1) / ↑R(k, l)) Filter.atTop (nhds 1)

graph theorypossible7 sources

declared proved (Lean) · formalizederdos:1022

False ↔ ∃ c, Filter.Tendsto c Filter.atTop Filter.atTop ∧ ∀ (t : ℕ), Erdos1022.SparseImpliesPropertyB t (c t)

combinatoricshypergraphspossible6 sources

declared solved (Lean) · formalizederdos:1023

True ↔ ∃ c, 0 < c ∧ Asymptotics.IsEquivalent Filter.atTop (fun n => ↑(Erdos1023.F n)) fun n => c * 2 ^ n / ↑n ^ (1 / 2)

combinatoricsA347025 · possible5 sources

declared solved (Lean) · formalizederdos:1026

For a sequence of

n

distinct reals, determine the largest constant

c

such that some monotonic subsequence always has sum exceeding

(c-o(1))\cdot(1/\sqrt{n})

times the total sum. Resolved as

c = 1

combinatoricsA391431 · A3914906 sources

declared solved (Lean) · formalizederdos:1028

(fun n => ↑(Erdos1028.H n)) =Θ[Filter.atTop] fun n => ↑n ^ (3 / 2)

graph theorydiscrepancypossible5 sources

declared openerdos:1032

Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?

graph theorychromatic numberpossible3 sources

declared openerdos:1033

Erdős problem 1033

graph theorypossible2 sources

declared disproved (Lean) · formalizederdos:1034

False ↔ ∀ (ε : ℝ), 0 < ε → ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑n ^ 2 / 4 < ↑G.edgeSet.ncard → ∃ T, G.IsNClique 3 T ∧ ∃ Y, Erdos1034.JoinedToTwo G T Y ∧ (1 / 2 - ε) * ↑n < ↑Y.card

graph theorypossible5 sources

declared proved (Lean) · formalizederdos:1036

True ↔ ∀ (c : ℝ), 0 < c → ∃ δ, 0 < δ ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑G.cliqueNum ≤ c * Real.log ↑n → ↑G.indepNum ≤ c * Real.log ↑n → Erdos1036.HasManyNonIsomorphicInducedSubgraphs G (2 ^ (δ * ↑n))

graph theorypossible5 sources

declared disproved (Lean) · formalizederdos:1037

False ↔ ∀ (ε : ℝ), 0 < ε → ∀ (C : ℝ), ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), (∀ (d : ℕ), {v | (G.neighborSet v).ncard = d}.ncard ≤ 2) → (1 / 2 + ε) * ↑n < ↑(Set.range fun v => (G.neighborSet v).ncard).ncard → ∃ s, Erdos1037.IsTrivialSet G s ∧ C * Real.log ↑n < ↑s.ncard

graph theoryN/A5 sources

declared open · formalizederdos:1038

Among all nonconstant monic polynomials

f

whose roots lie in

[-1, 1]

, determine

\inf_f |\{x \in \mathbb{R} : |f(x)| < 1\}|

analysisN/A4 sources

declared openerdos:1039

For

f(z) = \prod_{i=1}^n (z - z_i)

with all

|z_i| \le 1

, let

\rho(f)

be the radius of the largest disc contained in

\{z : |f(z)| < 1\}

. Is

\rho(f) \gg 1/n

? The worst case is now known to be

\Theta(1/n)

, with the explicit bound

\rho(f) \ge (\log 2)/n

analysisN/A3 sources

Problems · Vela Mathematics Program

Problem ledger

Search problems.science