Vela Mathematics Program: problems

Narrowed toformalized ×source:erdos-problems ×Clear all

Problem ledger

604 problems · 9/13Number SourcesGraph view

declared disproved (Lean) · formalizederdos:753

False ↔ ∃ c, 0 < c ∧ ∀ (n : ℕ), 0 < n → ∀ (G : SimpleGraph (Fin n)), ↑n ^ (1 / 2 + c) < ↑(Erdos753.listChromaticNumber G) + ↑(Erdos753.listChromaticNumber Gᶜ)

graph theorychromatic numberN/A5 sources

declared proved · formalizederdos:755

True ↔ ∃ o, (o =o[Filter.atTop] fun x => 1) ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ↑(Erdos755.TUnit 6 n) ≤ (1 / 27 + o n) * ↑n ^ 3

geometrypossible2 sources

declared proved (Lean) · formalizederdos:756

True ↔ (fun n => ↑n) =O[Filter.atTop] fun n => ↑(Erdos756.maxRichDistances n)

geometrydistancespossible5 sources

declared open · formalizederdos:757

∀ {A : Set ℝ}, sorry = sSup {c | Erdos757.IsAdmissible c}

geometrydistancessidon setspossible2 sources

declared proved (Lean) · formalizederdos:760

True ↔ ∃ c > 0, ∀ (V : Type u_1) [Finite V] (G : SimpleGraph V) (m : ℕ), G.chromaticNumber = ↑m → ∃ H k, ↑k ≤ H.coe.cochromaticNumber ∧ c * ↑m / Real.log ↑m ≤ ↑k

graph theorychromatic numberN/A5 sources

declared disproved (Lean) · formalizederdos:762

False ↔ ∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V), G.CliqueFree 5 → 4 ≤ G.cochromaticNumber → G.chromaticNumber ≤ G.cochromaticNumber + 2

graph theorychromatic numberN/A5 sources

declared open · formalizederdos:769

For the least cutoff

c(n)

after which every

k

occurs as the number of homothetic cubes in a decomposition of the unit

n

-cube, is

c(n) \gg n^n

? The Lean proof shows

c(n) = o(n^n)

along odd dimensions.

number theorygeometryA014544 · possible4 sources

declared open · formalizederdos:770

∀ {n : ℕ}, 2 < n → (Erdos770.h n = ↑n + 1 ↔ Nat.Prime (n + 1))

number theoryA263647 · possible2 sources

declared open · formalizederdos:774

True ↔ ∀ (A : Set ℕ), A.Infinite → A.IsProportionatelyDissociated → ∃ T, (∀ S ∈ T, S.IsDissociated) ∧ T.Finite ∧ A = ⋃₀ T

number theoryN/A2 sources

declared disproved (Lean) · formalizederdos:775

False ↔ ∃ C, ∃ᶠ (n : ℕ) in Filter.atTop, ∃ H, n - C ≤ H.cliqueSizes.ncard

graph theoryhypergraphspossible5 sources

declared falsifiable · formalizederdos:779

∀ n ≥ 1, have P := ∏ i ∈ Finset.range (n + 1), Nat.nth Nat.Prime i; ∃ p, Nat.Prime p ∧ Nat.Prime (P + p) ∧ Nat.nth Nat.Prime n < p ∧ p < P

number theoryprimesA0052352 sources

declared proved (Lean) · formalizederdos:785

True ↔ ∀ (A B : Set ℕ), A.Infinite → B.Infinite → Erdos785.IsExactAdditiveComplement A B → Filter.Tendsto (fun x => ↑(Erdos785.counting A x) * ↑(Erdos785.counting B x) - ↑x) Filter.atTop Filter.atTop

additive combinatoricsN/A5 sources

declared open · formalizederdos:786

Erdos786.consecutivePrimesFrom 2 1 = {2, 3}

number theoryA143301 · possible2 sources

declared open · formalizederdos:789

(fun n => ↑(Erdos789.subsetSumThreshold n)) =Θ[Filter.atTop] sorry

additive combinatoricspossible2 sources

declared disproved (Lean) · formalizederdos:794

False ↔ ∀ (n : ℕ) (H : Finset (Finset (Fin (3 * n)))), H.IsThreeUniform → n ^ 3 + 1 ≤ H.card → H.ContainsSubgraph 4 3 ∨ H.ContainsSubgraph 5 7

graph theoryhypergraphsturan numberN/A5 sources

declared open · formalizederdos:796

g_3(n)

is the largest size of

A \subseteq [1,n]

with fewer than three representations of every product

a_1 a_2

, does its conjectured second-order normalized term converge? The candidate proof gives an explicit limit constant.

number theorypossible5 sources

declared proved (Lean) · formalizederdos:798

True ↔ (fun n => ↑(Erdos798.t n)) =o[Filter.atTop] fun n => ↑n

geometryA1164465 sources

declared open · formalizederdos:812

True ↔ ∃ c > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ↑(Combinatorics.hypergraphRamsey 2 (n + 1)) / ↑(Combinatorics.hypergraphRamsey 2 n) ≥ 1 + c

graph theoryramsey theoryA0594422 sources

declared open · formalizederdos:817

True ↔ (fun n => 3 ^ n) =O[Filter.atTop] fun n => ↑(Erdos817.g 3 n)

additive combinatoricspossible2 sources

declared proved (Lean) · formalizederdos:818

True ↔ ∀ (K : ℝ), 0 < K → ∃ C, 0 < C ∧ ∃ c, 0 < c ∧ ∀ (A : Finset ℤ), 2 ≤ A.card → ↑(A + A).card ≤ K * ↑A.card → c * ↑A.card ^ 2 / Real.log ↑A.card ^ C ≤ ↑(A * A).card

additive combinatoricsN/A5 sources

declared open · formalizederdos:821

True ↔ ∀ ε > 0, {n | ↑(Erdos821.g n) > ↑n ^ (1 - ε)}.Infinite

number theoryA0141972 sources

declared proved · formalizederdos:822

True ↔ (Set.range fun n => n + n.totient).HasPosDensity

number theoryA121048 · A1550852 sources

declared proved · formalized · $25erdos:825

True ↔ ∃ C, ∃ (_ : C > 0), ∀ (n : ℕ), ↑((ArithmeticFunction.sigma 1) n) > C * ↑n → ∃ s ⊆ n.properDivisors, n = s.sum id

number theoryA006037 · A3302442 sources

declared open · formalizederdos:826

True ↔ ∃ C > 0, {n | ∀ k ≥ 1, ↑((ArithmeticFunction.sigma 0) (n + k)) ≤ C * ↑k}.Infinite

number theoryN/A2 sources

declared open · formalizederdos:828

True ↔ ∀ (a : ℤ), {n | ↑n.totient ∣ ↑n + a}.Infinite

number theoryN/A2 sources

declared open · formalizederdos:829

True ↔ ∃ C, (fun n => ↑(AdditiveCombinatorics.sumRep Erdos829.cubes n)) =O[Filter.atTop] fun n => Real.log ↑n ^ C

number theorypossible2 sources

declared open · formalizederdos:830

sorry ↔ {(a, b) | IsAmicable a b}.Infinite

number theoryA2591802 sources

declared verifiable · formalizederdos:835

∀ {k : ℕ}, 3 ≤ k → k ≤ 8 → ↑k + 1 < (SimpleGraph.johnson (2 * k) k).chromaticNumber

graph theoryhypergraphsN/A3 sources

declared proved (Lean) · formalizederdos:844

True ↔ ∀ (N : ℕ), IsGreatest {k | ∃ A ⊆ Finset.Icc 1 N, (∀ a ∈ A, ∀ b ∈ A, ¬Squarefree (a * b)) ∧ A.card = k} (Erdos844.evenOrOddNonSquarefree N).card

number theoryintersecting familyN/A5 sources

declared disproved (Lean) · formalizederdos:845

False ↔ ∀ (C : ℝ), 0 < C → have f := fun x => match x with | (k, l) => 2 ^ k * 3 ^ l; {x | ∃ B, ∃ (h : B.Nonempty) (_ : ↑(B.sup f) ≤ C * ↑(B.inf' h f)), ∑ x ∈ B, f x = x}.HasDensity 0

number theoryN/A5 sources

declared disproved (Lean) · formalizederdos:846

False ↔ ∀ (A : Set (EuclideanSpace ℝ (Fin 2))), ∀ ε > 0, A.Infinite → Erdos846.NonTrilinearFor A ε → Erdos846.WeaklyNonTrilinear A

geometryN/A6 sources

declared disproved · formalizederdos:847

False ↔ ∀ (A : Set ℕ), Infinite ↑A → Erdos847.HasFew3APs A → ∃ n S, (∀ (i : Fin n), ThreeAPFree (S i)) ∧ A = ⋃ i, S i

additive combinatoricsN/A3 sources

declared decidable · formalizederdos:848

Is the maximum size of a set

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

such that

ab+1

is never squarefree (for all

a,b\in A

) achieved by taking those

n\equiv 7\pmod{25}

? Resolved for all sufficiently large

N

: any near-maximal

A

is contained in

\{n\equiv 7\pmod{25}\}

\{n\equiv 18\pmod{25}\}

, leaving only a finite check.

number theoryN/A4 sources

declared open · formalizederdos:849

True ↔ ∀ t ≥ 1, ∃ a, {n | ∃ k ≥ 1, 2 * k ≤ n ∧ n.choose k = a}.ncard = t

number theorybinomial coefficientsA003016 · A003015 · A059233 · A098565 · A090162 · A180058 · A1822372 sources

declared open · formalizederdos:850

True ↔ ∃ x y, x ≠ y ∧ x.primeFactors = y.primeFactors ∧ (x + 1).primeFactors = (y + 1).primeFactors ∧ (x + 2).primeFactors = (y + 2).primeFactors

number theoryprimesA3431013 sources

declared proved · formalizederdos:851

∀ ε ∈ Set.Ioo 0 1, ∃ r d, (Erdos851.TwoPowAddSet r).HasDensity d ∧ 1 - ε ≤ d

number theoryN/A4 sources

declared open · formalizederdos:853

Filter.Tendsto Erdos853.r Filter.atTop Filter.atTop

number theoryprimesA001223 · A3907692 sources

declared open · formalizederdos:855

True ↔ ∀ᶠ (x : ℕ) (y : ℕ) in Filter.atTop, (x + y).primeCounting ≤ x.primeCounting + y.primeCounting

number theoryprimesA0231932 sources

declared open · formalizederdos:857

have f := sorry; ∀ (k : ℕ), 3 ≤ k → Filter.Tendsto (fun n => ↑(Erdos857.m n k) / f k n) Filter.atTop (nhds 1)

combinatoricspossible2 sources

declared open · formalizederdos:859

∃ c₁ > 0, ∃ c₂ > 0, ∃ d, (∀ t > 0, (Erdos859.DivisorSumSet t).HasDensity (d t)) ∧ Asymptotics.IsEquivalent Filter.atTop (fun t => d t) fun t => c₁ / Real.log ↑t ^ c₂

number theorydivisorsN/A2 sources

declared solved (Lean) · formalizederdos:862

False ↔ (fun N => Real.logb 2 ↑(Erdos862.numMaximalSidonSets N)) =o[Filter.atTop] fun N => ↑N ^ (1 / 2)

number theorysidon setsA3823955 sources

declared proved (Lean) · formalizederdos:865

∃ C > 0, ∀ᶠ (N : ℕ) in Filter.atTop, ∀ A ⊆ Finset.Icc 1 N, ↑A.card ≥ 5 / 8 * ↑N + C → ∃ a ∈ A, ∃ b ∈ A, ∃ c ∈ A, a ≠ b ∧ a ≠ c ∧ b ≠ c ∧ a + b ∈ A ∧ a + c ∈ A ∧ b + c ∈ A

number theoryadditive combinatoricspossible5 sources

declared disproved (Lean) · formalizederdos:867

False ↔ ∃ C, ∀ (N : ℕ), ∀ A ⊆ Finset.Icc 1 N, Erdos867.ConsecutiveSumFree A → ↑A.card ≤ ↑N / 2 + C

additive combinatoricspossible5 sources

declared solved · formalizederdos:868

False ↔ ∀ (A : Set ℕ), A.IsAsymptoticAddBasisOfOrder 2 → Filter.Tendsto (fun n => Erdos868.ncard_add_repr A 2 n) Filter.atTop Filter.atTop → ∃ B ⊆ A, B.IsAsymptoticAddBasisOfOrder 2 ∧ ∀ b ∈ B, ¬(B \ {b}).IsAsymptoticAddBasisOfOrder 2

number theoryadditive basisN/A3 sources

declared disproved (Lean) · formalizederdos:871

False ↔ ∀ (A : Set ℕ), ((∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ A, ∃ b ∈ A, a + b = n) ∧ ∀ (t : ℕ), ∀ᶠ (n : ℕ) in Filter.atTop, ∃ pairs, pairs.card ≥ t ∧ ∀ p ∈ pairs, p.1 ∈ A ∧ p.2 ∈ A ∧ p.1 + p.2 = n ∧ p.1 ≤ p.2) → ∃ B C, (∀ (x : ℕ), x ∈ A ↔ x ∈ B ∨ x ∈ C) ∧ Disjoint B C ∧ (∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ B, ∃ b ∈ B, a + b = n) ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ∃ a ∈ C, ∃ b ∈ C, a + b = n

number theoryadditive basisN/A6 sources

declared open · formalizederdos:872

True ↔ ∃ ε > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ↑(Erdos872.L n) ≥ ε * ↑n

number theoryprimitive setspossible3 sources

declared open · formalizederdos:873

True ↔ ∀ (a : ℕ → ℕ), ∀ ε > 0, 0 < a 0 → StrictMono a → ∃ k, ∀ X > 0, ↑↑(Erdos873.F a X k) < ↑(X ^ ε)

number theoryN/A3 sources

declared open · formalizederdos:881

True ↔ ∀ (k : ℕ) (A : Set ℕ), Erdos881.IsMinimalAsymptoticAddBasisOfOrder k A → ∃ B ⊆ A, B.Infinite ∧ (A \ B).IsAsymptoticAddBasisOfOrder (k + 1)

number theoryadditive basisN/A2 sources

declared disproved (Lean) · formalizederdos:884

False ↔ Erdos884.Erdos884Prop

number theorydivisorsN/A3 sources

declared open · formalizederdos:885

True ↔ ∀ k ≥ 1, ∃ Ns, (∀ n ∈ Ns, 1 ≤ n) ∧ Ns.card = k ∧ (⋂ n ∈ Ns, Erdos885.factorDifferenceSet n).ncard ≥ k

number theorydivisorsN/A2 sources

Problems · Vela Mathematics Program

Problem ledger

Search problems.science