Skip to content

Problems · Vela Mathematics Program

Narrowed toadditive combinatorics ×source:vibemathed ×Clear all

Problem ledger

11 problemsGraph view
declared solved (Lean) · formalizederdos:42
True ↔ ∀ M ≥ 1, ∀ᶠ (N : ℕ) in Filter.atTop, ∀ (A : Set ℕ), A.IsMaximalSidonSetIn N → ∃ B ⊆ Set.Icc 1 N, IsSidon B ∧ B.ncard = M ∧ (A - A) ∩ (B - B) = {0}
number theorysidon setsadditive combinatoricsN/A6 sources
declared disproved · formalized · $100erdos:43
If Sidon sets A,B⊆{1,…,N}A, B \subseteq \{1, \dots, N\} satisfy (A−A)∩(B−B)={0}(A-A) \cap (B-B) = \{0\}, must (∣A∣2)+(∣B∣2)≤(f(N)2)+O(1)\binom{|A|}{2} + \binom{|B|}{2} \le \binom{f(N)}{2} + O(1), where f(N)f(N) is the largest Sidon-set size in [N][N] - and can the bound be improved by a fixed proportion when ∣A∣=∣B∣|A| = |B|?
number theorysidon setsadditive combinatoricsA143824 · A227590 · A003022 · possible4 sources
declared open · formalized · $500erdos:138
If W(k)W(k) is the least NN such that every two-colouring of {1,…,N}\{1, \dots, N\} contains a monochromatic kk-term arithmetic progression, must W(k+1)−W(k)→∞W(k+1) - W(k) \to \infty?
additive combinatoricsA0053464 sources
declared openerdos:176
Let N(k,ℓ)N(k, \ell) be the least NN such that every f:[N]→{−1,1}f : [N] \to \{-1, 1\} has a kk-term arithmetic progression PP with ∣∑n∈Pf(n)∣≥ℓ|\sum_{n \in P} f(n)| \ge \ell. In particular, is N(k,2)≤CkN(k, 2) \le C^k?
additive combinatoricsarithmetic progressionsdiscrepancypossible3 sources
declared disproved (Lean) · formalized · $1000erdos:707
Erdős conjectured, in over a dozen papers spanning 1976 to 1997 and with a 1000 dollars prize attached, that every finite Sidon set extends to a perfect difference set modulo p2+p+1p^2+p+1 for some prime pp. Alexeev and Mixon establish that {1,2,4,8}\{1,2,4,8\} is a counterexample - and discovered along the way that Marshall Hall, Jr. had published a different counterexample three decades before Erdős first posed the problem, unnoticed by the community for half a century.
additive combinatoricssidon setsN/A6 sources
declared solved (Lean) · formalizederdos:741
True ↔ ∀ (A : Set ℕ), 0 < (A + A).upperDensity → ∃ A₁ A₂, A = A₁ ∪ A₂ ∧ Disjoint A₁ A₂ ∧ 0 < (A₁ + A₁).upperDensity ∧ 0 < (A₂ + A₂).upperDensity
additive combinatoricsN/A6 sources
declared provederdos:863
Erdős problem 863
number theorysidon setsadditive combinatoricsN/A3 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 openerdos:866
Estimate the least excess gk(N)g_k(N) forcing kk integers whose pairwise sums all lie in a dense subset of {1,…,2N}\{1, \dots, 2N\}; in particular, determine the positive variant h4(n)h_4(n).
number theoryadditive combinatoricspossible5 sources
declared proved (Lean) · formalizederdos:966
Let k,r≥2k,r\geq 2. Does there exist a set A⊆NA\subseteq \mathbb{N} that contains no non-trivial arithmetic progression of length k+1k+1, yet in any rr-colouring of AA there must exist a monochromatic non-trivial arithmetic progression of length kk? Answered in the affirmative.
number theoryadditive combinatoricsramsey theoryN/A6 sources
declared openerdos:1186
What is the minimum asymptotic density δk\delta_k of monochromatic kk-term arithmetic progressions in every two-colouring of {1,…,n}\{1, \dots, n\}? The exact certificate gives δ3=117/2192\delta_3 = 117/2192, matching the known 548-bead colouring.
additive combinatoricsarithmetic progressionspossible2 sources