Erdős Problem #357
Let f(n) be the maximal k such that there exist integers 1 ≤ a_1 < dotsc < a_k ≤ n such that all sums of the shape Σ_u ≤ i ≤ v a_i are distinct. Is f(n)=o(n)?
No claims yet Be the first →
Formal Conjectures: open problems with Lean statements
Formal Conjectures is an open repository, started by Google DeepMind, of conjectures stated in Lean 4 with Mathlib. Every open problem from it that we import keeps its exact Lean statement, so a proof submitted here is checked by the Lean kernel against that statement. The collection covers Erdős problems, OEIS conjectures, Ben Green's open problems, Wikipedia's lists of unsolved problems, MathOverflow questions and more.
Source: google-deepmind/formal-conjectures. Licence: Apache License 2.0.
Erdős Problem #359
Let a_1< a_2 < ⋯ be an infinite sequence of integers such that a_1=1 and a_i+1 is the least integer which is not a sum of consecutive earlier a_js. Show that a_k / k → ∞.
No claims yet Be the first →
Erdős Problem #361
Let c > 0 and n be some large integer. What is the size of the largest set A ⊆ 1, …, ⌊ c n ⌋ such that n is not a sum of a subset of A? Does this depend on n in an irregular way?
No claims yet Be the first →
Erdős Problem #364
There is no consecutive triple of powerful numbers.
No claims yet Be the first →
Erdős Problem #366
Are there any 2-full n such that n+1 is 3-full?
No claims yet Be the first →
Erdős Problem #367
Let B_2(n) be the 2-full part of n (that is, B_2(n)=n/n' where n' is the product of all primes that divide n exactly once). Is it true that, for every fixed k ≥ 1, Π_n ≤ m < n+k B_2(m) ≪ n^2+o(1)?
No claims yet Be the first →
Erdős Problem #371
Let P(n) denote the largest prime factor of n. Show that the set of n with P(n+1) > P(n) has density 1/2.
No claims yet Be the first →
Erdős Problem #373
Show that the equation n!=a_1!a_2!···a_k!, with n−1 > a_1 ≥ a_2 ≥ ··· ≥ a_k, has only finitely many solutions.
No claims yet Be the first →
Erdős Problem #375
Is Erdos375Prop true?
No claims yet Be the first →
Erdős Problem #376
Are there infinitely many n such that 2nchoose n is coprime to 105?
No claims yet Be the first →
Erdős Problem #377
Is there some absolute constant C > 0 such that Σ_p ≤ n 1_pnmid 2n choose n1/p ≤ C for all n?
No claims yet Be the first →
Erdős Problem #383
Is it true that for every k there are infinitely many primes p such that the largest prime divisor of Π_i = 0^k (p ^ 2 + i) is p?
No claims yet Be the first →
Erdős Problem #385
Let F(n) := maxm + p(m) | textrmm < n composite where p(m) is the least prime divisor of m. Is it true that F(n)>n for all sufficiently large n?
No claims yet Be the first →
Erdős Problem #386
Let 2 ≤ k ≤ n - 2. Can C(n, k) be the product of consecutive primes infinitely often? Here k may vary with n: the question asks for infinitely many admissible binomial coefficients, not for a single k that works infinitely often.
No claims yet Be the first →
Erdős Problem #389
Is it true that for every n ≥ 1 there is a k such that n(n + 1) ⋯ (n + k - 1) | (n + k) ⋯ (n + 2k - 1)?
No claims yet Be the first →
Erdős Problem #39
Is there an infinite Sidon set A⊂ ℕ such that lvert A∩ 1…,Nrvert ≫_ε N^1/2-ε for all ε > 0?
No claims yet Be the first →
Erdős Problem #390
Does there exists a constant c such that f n - 2 n ~ c (n / log n)?
No claims yet Be the first →
Erdős Problem #396
Is it true that for every k there exists n such that Π_0≤ i≤ k(n-i) | C(2n, n)?
No claims yet Be the first →
Erdős Problem #398
Brocard's Problem Does n! + 1 = m^2 have integer solutions other than n = 4, 5, 7?
No claims yet Be the first →
Erdős Problem #40
For what functions g(N) → ∞ is it true that lvert A∩ 1,…,Nrvert ≫ N^1/2/g(N) implies limsup 1_Aast 1_A(n)=∞?
No claims yet Be the first →
Erdős Problem #400
Can one show that Σ_n≤ xg_k(n) ∼ c_k xlog x for some constant c_k?
No claims yet Be the first →
Erdős Problem #406
Is it true that there are only finitely many powers of 2 which have only the digits 0 and 1 when written in base 3?
No claims yet Be the first →
Erdős Problem #409
Erdős Problem #409
No claims yet Be the first →
Erdős Problem #41
Let A ⊂ ℕ be an infinite set such that the triple sums a+b+c are all distinct for a,b,c ∈ A (aside from the trivial coincidences). Is it true that liminf_N → ∞ fraclvert A ∩ 1,…,NrvertN^1/3=0?
No claims yet Be the first →
Erdős Problem #410
Let σ_1(n) = σ(n), the sum of divisors function, and σ_k(n) = σ(σ_k-1(n)). Is it true that lim_k → ∞ σ_k(n)^frac 1 k = ∞?
No claims yet Be the first →
Erdős Problem #412
Let σ_1(n)=σ(n), the sum of divisors function, and σ_k(n) = σ(σ_k-1(n)). Is it true that, for every m, n ≥ 2, there exist some i, j such that σ_i(m) = σ_j(n)?
No claims yet Be the first →
Erdős Problem #413
Are there infinitely many barriers for ω?
No claims yet Be the first →
Erdős Problem #414
Let h_1(n) = h(n) and h_k(n) = h(h_k-1(n)). Is it true, for any m,n, there exist i and j such that h_i(m) = h_j(n)?
No claims yet Be the first →
Erdős Problem #416
Let V(x) count the number of n≤x such that ϕ(m)=n is solvable. Does V(2x)/V(x)→2 ?
No claims yet Be the first →
Erdős Problem #417
LetV'(x)=\#φ(m) : 1≤ m≤ xandV(x)=\#φ(m) ≤ x : 1≤ m. Does lim V(x)/V'(x) exist?
No claims yet Be the first →
Erdős Problem #422
Let f(1) = f(2) = 1 and for n > 2 f(n) = f(n - f(n - 1)) + f(n - f(n - 2)). Does f(n) miss infinitely many integers?
No claims yet Be the first →
Erdős Problem #423
Erdős Problem 423 [Er77c, p.71; ErGr80, p.83]: Let a(1) = 1, a(2) = 2, and for k ≥ 3 let a(k) be the least integer greater than a(k-1) that is a sum of at least two consecutive terms of the sequence. What is the asymptotic behaviour of this sequence? It seems likely that a_n = n + o(n).
No claims yet Be the first →
Erdős Problem #428
Is there a set A⊆ ℕ such that, for infinitely many n, all of n-a are prime for all a∈ A with 0 < a < n and liminflvert A∩ [1,x]rvert/π(x)>0?
No claims yet Be the first →
Erdős Problem #431
Are there two infinite sets A and B such that A+B agrees with the primes up to finitely many exceptions?
No claims yet Be the first →
Erdős Problem #44
Erdős Problem 44: Let N ≥ 1 and A ⊆ 1,…,N be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and B ⊆ N+1,…,M such that A ∪ B ⊆ 1,…,M is a Sidon set of size at least (1−ε)M^1/2?
No claims yet Be the first →
Erdős Problem #445
Is it true that, for any c>1/2, if p is a sufficiently large prime then, for any n≥ 0, there exist a,b∈(n,n+p^c) such that ab≡ 1pmodp? This is discussed in this MathOverflow question [MathOverflow].
No claims yet Be the first →
Erdős Problem #450
How large must y=y(ε,n) be such that the number of integers in (x,x+y) with a divisor in (n,2n) is at most ε y? The bound is required for every x and every window length at least y, and y(ε,n) is the least such threshold (or ∞ if there is none).
No claims yet Be the first →
Erdős Problem #452
Determine the largest length of an interval in [x,2x] on which ω(n) > loglog n everywhere.
No claims yet Be the first →
Erdős Problem #454
Is it true that limsup (fun n => (f n - 2 * n.nth Prime : ℕ∞)) atTop = ⊤?
No claims yet Be the first →
Erdős Problem #455
Let q : ℕ → ℕ be a strictly increasing sequence of primes such that q (n + 2) - q (n + 1) ≥ q (n + 1) - q n. Must lim q n / (n ^ 2) = ∞?
No claims yet Be the first →
Erdős Problem #456
Is it true that m_n<p_n for almost all n?
No claims yet Be the first →
Erdős Problem #458
Let lcm(1, …, n) denote the least common multiple of 1, …, n. Let p_k be the k-th prime. Is it true that for all k ≥ 1, lcm(1, …, p_k+1-1) < p_k · lcm(1, …, p_k)?
No claims yet Be the first →
Erdős Problem #462
Let p(n) denote the least prime factor of n. Is there a constant C>0 such that Σ_x≤ n≤ x+C√(x)(log x)^2p(n)/n≫ 1 for all sufficiently large x?
No claims yet Be the first →
Erdős Problem #463
Is there a function f with f(n)→∞ as n→∞ such that, for all large n, there is a composite number m such that n + f(n) < m < n + p(m) Here p(m) is the least prime factor of m.
No claims yet Be the first →
Erdős Problem #470
Are there any odd weird numbers?
No claims yet Be the first →
Erdős Problem #478
Let p be a prime and A_p = k! pmodp : 1≤ k<p. Is it true that lvert A_prvert ∼ (1-1/e)p?
No claims yet Be the first →
Erdős Problem #479
Is it true that, for every integer k≠ 1, there are infinitely many n such that 2^n≡ kpmodn?
No claims yet Be the first →
Erdős Problem #488
Let A be a finite set and B= n ≥ 1 : a| ntextrm for some a∈ A. Is it true that, for every m>n≥ max(A), lvert B∩ [1,m]rvert /m< 2lvert B∩ [1,n]rvert/n?
No claims yet Be the first →
Erdős Problem #495
Let α,β ∈ ℝ. Is it true thatliminf_n→ ∞ n ‖ nα ‖ ‖ nβ‖ =0? This is also known as the Littlewood conjecture.
No claims yet Be the first →
Erdős Problem #5
Let C≥ 0. Is there an infinite sequence of n_i such that lim_i→ inftyp_n_i+1-p_n_i/log n_i=C? We formalise "an infinite sequence of n_i" as a strictly monotone sequence of indices n : ℕ → ℕ.
No claims yet Be the first →
Erdős Problem #50
Let f be the asymptotic distribution function of φ(n)/n, so that for each c ∈ [0,1], f(c) is the natural density of n : φ(n) < cn. Is it true that there is no x such that the derivative f'(x) exists and is positive?
No claims yet Be the first →
Erdős Problem #501
For every x ∈ ℝ let A_x ⊂ ℝ be a bounded set with outer measure < 1. Must there exist an infinite independent set, that is, some infinite X ⊆ ℝ such that x ∉ A_y for all x ≠ y ∈ X? If the sets A_x are closed and have measure < 1, then must there exist an independent set of size 3?
No claims yet Be the first →
Erdős Problem #503
What is the size of the largest A ⊆ ℝ^n such that every three points from A determine an isosceles triangle? That is, for any three points x, y, z from A, at least two of the distances |x - y|, |y - z|, |x - z| are equal.
No claims yet Be the first →
Erdős Problem #506
Erdős Problem #506
No claims yet Be the first →
Erdős Problem #507
Let α(n) be such that every set of n points in the unit disk contains three points which determine a triangle of area at most α(n). Estimate α(n).
No claims yet Be the first →
Erdős Problem #508
The Hadwiger–Nelson problem asks: How many colors are required to color the plane such that no two points at distance 1 from each other have the same color?
No claims yet Be the first →
Erdős Problem #509
Let f(z) ∈ ℂ[z] be a monic non-constant polynomial. Can the set z ∈ ℂ : |f(z)| ≤ 1 be covered by a set of closed discs the sum of whose radii is ≤ 2?
No claims yet Be the first →
Erdős Problem #51
Is there an infinite set A ⊂ ℕ such that for every a ∈ A, there is an integer n such that φ(n)=a, and yet if n_a is the smallest such integer, then n_a/a → ∞ as a → ∞?
No claims yet Be the first →
Erdős Problem #510
Chowla's cosine problem If A⊂ ℕ is a finite set of positive integers of size N > 0 then is there some absolute constant c>0 and θ such that Σ_n∈ Acos(nθ) < -cN^1/2?
No claims yet Be the first →
Erdős Problem #513
Let f be a transcendental entire function. What is the greatest possible value of liminf (fun r : ℝ => ratio r f) atTop?
No claims yet Be the first →
Erdős Problem #517
If f(z) = ∑ aₖzⁿₖ is an entire function (with aₖ ≠ 0 for all k) such that nₖ / k → ∞, is it true that f assumes every value infinitely often?
No claims yet Be the first →
Erdős Problem #52
Let A be a finite set of integers. Is it true that for every ε>0 max( lvert A+Arvert,lvert AArvert)≫_ε lvert Arvert^2-ε?
No claims yet Be the first →
Erdős Problem #522
Let f(z)=Σ_0≤ k≤ n ε_k z^k be a random polynomial, where ε_k∈ -1,1 independently uniformly at random for 0≤ k≤ n. Is it true that, if R_n is the number of roots of f(z) in z∈ ℂ : lvert zrvert ≤ 1, then R_n/n/2→ 1 almost surely?
No claims yet Be the first →
Erdős Problem #535
Let r ≥ 3, and let f_r(N) denote the size of the largest subset of 1,…,N such that no subset of size r has the same pairwise greatest common divisor between all elements.
No claims yet Be the first →
Erdős Problem #536
Let ε>0 and N be sufficiently large. Is it true that if A⊆ 1,…,N has size at least ε N then there must be distinct a,b,c∈ A such that [a, b]=[b, c]=[a, c], where [·, ·] denotes the least common multiple?
No claims yet Be the first →
Erdős Problem #538
Let r≥ 2 and suppose that A⊆1,…,N is such that, for any m, there are at most r solutions to m=pa where p is prime and a∈ A. Give the best possible upper bound for Σ_n∈ A1/n. Erdős observed that Σ_n∈ A1/n≪ rlog N/loglog N, and the order Θ_r(log N / loglog N) is known (see erdos_538.matching_order).
No claims yet Be the first →
Erdős Problem #539
Let h(n) be maximal such that, for any set A⊆ ℕ of size n, the set a/(a,b): a,b∈ Ahas size at least h(n). Estimate h(n).
No claims yet Be the first →
Erdős Problem #544
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #545
Let m be sufficiently large and let G be a graph with m edges and no isolated vertices. Is the Ramsey number R(G) maximised when G is 'as complete as possible'?
No claims yet Be the first →
Erdős Problem #551
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #552
Determine the Ramsey number R(C_4, S_n), where S_n=K_1,n is the star on n+1 vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #562
Let R_r(n) denote the r-uniform hypergraph Ramsey number: the minimal m such that if we 2-colour all edges of the complete r-uniform hypergraph on m vertices then there must be some monochromatic copy of the complete r-uniform hypergraph on n vertices.
No claims yet Be the first →
Erdős Problem #563
Let F(n,α) denote the smallest m such that there exists a 2-colouring of the edges of K_n so that every X⊆ [n] with lvert Xrvert≥ m contains more than α C(lvert Xrvert, 2) many edges of each colour. Prove that, for every 0≤ α < 1/2, F(n,α)∼ c_αlog n for some constant c_α depending only on α.
No claims yet Be the first →
Erdős Problem #564
Let R_3(n) be the minimal m such that if the edges of the 3-uniform hypergraph on m vertices are 2-coloured then there is a monochromatic copy of the complete 3-uniform hypergraph on n vertices. Is there some constant c>0 such that R_3(n) ≥ 2^2^cn?
No claims yet Be the first →
Erdős Problem #566
Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
No claims yet Be the first →
Erdős Problem #567
Erdős Problem 567 (Q3) Is Q_3 (the 3-dimensional hypercube) Ramsey size linear?
No claims yet Be the first →
Erdős Problem #568
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #569
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #572
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #579
Let δ > 0. If n is sufficiently large and G is a graph on n vertices with no K_2,2,2 (the octahedron) and at least δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
No claims yet Be the first →
Erdős Problem #583
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
No claims yet Be the first →
Erdős Problem #592
Determine which countable ordinals β have the property that, if α = ω^β, then in any red/blue colouring of the edges of K_α there is either a red K_α or a blue K_3.
No claims yet Be the first →
Erdős Problem #593
Erdős Problem 593 (\500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number > aleph_0. The answer is the set of obligatory finite 3-uniform hypergraphs, represented here on the labelled vertex sets Fin n.
No claims yet Be the first →
Erdős Problem #595
Erdős Problem 595 (\250): Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
No claims yet Be the first →
Erdős Problem #596
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
No claims yet Be the first →
Erdős Problem #598
Erdős Problem 598: Let m be an infinite cardinal and κ be the successor cardinal of 2^aleph_0. Can one colour the countable subsets of m using κ many colours so that every X ⊆ m with |X| = κ contains subsets of all possible colours?
No claims yet Be the first →
Erdős Problem #60
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
No claims yet Be the first →
Erdős Problem #600
Let r ≥ 2. Is it true that e(n,r+1) - e(n,r) → ∞ as n → ∞?
No claims yet Be the first →
Erdős Problem #602
Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B? Formally: let α be any type, let (A_i)_i ∈ I be a family of countably infinite subsets of α such that for all i ≠ j, the intersection A_i ∩ A_j is finite and |A_i ∩ A_j| ≠ 1.
No claims yet Be the first →
Erdős Problem #609
Let f(n) be the minimal m such that if the edges of K_2^n+1 are coloured with n colours then there must be a monochromatic odd cycle of length at most m. Estimate f(n).
No claims yet Be the first →
Erdős Problem #61
The Erdős–Hajnal Conjecture states that there is a constant c(H) > 0 for each H such that we can take f(n) = n^c(H) in the above formulation.
No claims yet Be the first →
Erdős Problem #617
Let r≥ 3. If the edges of K_r^2+1 are r-coloured then there exist r+1 vertices with at least one colour missing on the edges of the induced K_r+1. In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99].
No claims yet Be the first →
Erdős Problem #623
Let X be a set of cardinality aleph_ω and f be a function from the finite subsets of X to X such that f(A)not∈ A for all A. Must there exist an infinite Y⊆ X that is independent - that is, for all finite B⊂ Y we have f(B)not∈ Y?
No claims yet Be the first →
Erdős Problem #624
Let X be a finite set of size n and H(n) be such that there is a function f:A : A⊆ X→ X so that for every Y⊆ X with lvert Yrvert ≥ H(n) we have f(A) : A⊆ Y=X. Prove that H(n)-log_2 n → ∞.
No claims yet Be the first →
Erdős Problem #628
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
No claims yet Be the first →
Erdős Problem #64
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
No claims yet Be the first →
Erdős Problem #647
Let τ(n) count the number of divisors of n. Is there some n > 24 such that max_m < n(m + τ(m)) ≤ n + 2?
No claims yet Be the first →
Erdős Problem #65
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #653
Let x_1,…,x_n∈ ℝ^2 and let R(x_i)=\# lvert x_j-x_irvert : j≠ i, where the points are ordered such that R(x_1)≤ ⋯ ≤ R(x_n). Let g(n) be the maximum number of distinct values the R(x_i) can take. Is it true that g(n) ≥ (1-o(1))n?
No claims yet Be the first →
Erdős Problem #66
Is there and A ⊂ ℕ is such that lim_n→ ∞1_Aast 1_A(n)/log n exists and is ≠ 0?
No claims yet Be the first →