858 Discussion Thread | Erdős Problems

Alexander [Al66] and Erdős, Sárközi, and Szemerédi [ESS68] proved that if

𝐴

is an infinite set with this property then

\sum 𝑛 \in 𝐴 \cap [1, 𝑁] 1 𝑛 = 𝑜 (l o g 𝑁)

(at a rate which depends on

𝐴

), and furthermore for any fixed large

𝑁

the supremum in this question is bounded away from

0

.

This condition on

𝐴

is a weaker form of the usual primitive condition. If

𝐴

is primitive then Behrend [Be35] proved

1 l o g 𝑁 \sum 𝑛 \in 𝐴 1 𝑛 ≪ 1 \sqrt l o g l o g 𝑁 .

An example of such a set

𝐴

is the set of all integers in

[𝑁 1 / 2, 𝑁]

divisible by some prime

> 𝑁 1 / 2

.

This has been solved by Chojecki and GPT-5.4 Pro (see the comments), who show that for large

𝑁

m a x 𝐴 \sum 𝑛 \in 𝐴 1 𝑛 = (𝑐 + 𝑜 (1)) l o g 𝑁

where the maximum is over all

𝐴 \subseteq {1, \dots, 𝑁}

with the stated property and

𝑐 \approx 0.618 \dots

is an explicit constant.

See also [143].

View the LaTeX source

This page was last edited 24 April 2026. View history

Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)

This is the cleanest application of ideas from [1196] solution with sub-Markov chains. However I couldn't make it in one prompt, and the following note is a messy result of back-and-forth with multiple instances of GPT-5.4 Pro.

The main result is the estimate
$m a x 𝐴 \sum 𝑛 \in 𝐴 1 𝑛 = (𝑐 + 𝑜 (1)) l o g 𝑁$
together with some compute around it. If one cares only about the asymptotic result, then the proof can be significantly shortened as the arguments are easier asymptotically. I probably put that out too, and I'll work on formalization. I wanted to share the longer note, because I think ideas there are interesting.

EDIT: Here's a streamlined argument just for the asymptotic part (and even more streamlined version here with sub-Markov chain argument made more elementary). Formalization by Aristotle of this streamlined argument is here. It formalizes sub-Markov chains/dynamic programming well, and leaves 2 sorries for Mertens and one analytic result (but informal proofs are given by Aristotle too).

Przemek Chojecki — 18:37 on 15 Apr 2026
- Thanks! I ran a standard check which pointed out a few minor issues. In general, GPT-5.4 Thinking seemed to have a bit of trouble checking it, likely because there's a lot of material (which means there's more chance of a missed error). In that sense a more streamlined/short/formalized version would be appreciated as well.
  
  Nat Sothanaphan — 19:43 on 15 Apr 2026
- I see the streamlined version now. Here is standard check which still claims some minor issues, but I would say with more confidence in overall correctness. I do think you're rushing a bit with these writeups though.
  
  Nat Sothanaphan — 20:29 on 15 Apr 2026
  - Thanks! Indeed, this and [856] were back to back, but just because they pretty much used the same method and I could try them concurrently. I'm currently waiting for the autoformalization results + experts' opinions.
    
    Przemek Chojecki — 20:32 on 15 Apr 2026
    - I've added the formalization above of the streamlined argument. Aristotle manages to formalize this funny Markov chain arguments without problem, but doesn't go into Mertens/analytic results and leave them as sorries with the reason of that not being in mathlib.
      
      Przemek Chojecki — 15:05 on 16 Apr 2026
      - I see there are 8 remaining sorries. Can you try to get them down to a few standard results whose statements are easily checkable?
        
        Nat Sothanaphan — 15:13 on 16 Apr 2026
        
        Yes, I'll try doing that.
        
        Przemek Chojecki — 15:26 on 16 Apr 2026
        
        Ok, I've just did that - replaced the previous formalization above (see EDIT) with the one with only 2 sorries that are standard (Mertens + one other thing) - and proved by Aristotle informally too. Also added a second even more streamlined version for the asymptotic, so that it can be even easier to check. I've been going back and forth with various LLMs on it, and can't really find any substantial error for the strategy/arguments for the main theorem.
        
        Przemek Chojecki — 15:51 on 17 Apr 2026
        
        I think Mertens is fine, but "sorry #2" (which secretly has 2 things) should be proved? I think we should reduce to standard theorems or known results in literature.
        
        Nat Sothanaphan — 16:03 on 17 Apr 2026
        
        Thanks for checking it, I'll try to do it separately then without Aristotle and see whether I can push it there with manual+LLMs direct formalization (focusing on missing sorry).
        
        Przemek Chojecki — 18:32 on 17 Apr 2026
- Here is a summary of the argument. One places a flow network on ${1, \dots, 𝑁}$ by creating a flow $𝑤 (𝑛 𝑝 1 \dots 𝑝 𝑘 \mapsto 𝑛) = 1 𝑛 𝑝 1 \dots 𝑝 𝑘$ if $𝑛 < 𝑝 1 \leq \dots \leq 𝑝 𝑘$ , but one does not have $𝑛 𝑝 1 \dots 𝑝 𝑖 - 1 < 𝑝 𝑖$ for any $1 < 𝑖 \leq 𝑘$ . Then the outflow at any $1 < 𝑛 \leq 𝑁$ is exactly $1 / 𝑛$ (with only one outgoing edge), and the downward flow from any $𝑛 \in 𝐴$ cannot hit any other element of $𝐴$ by hypothesis. Because of this, one can use the discrete divergence theorem to express $\sum 𝑛 \in 𝐴 1 𝑛$ as the sum of divergences $\sum 𝑛 \in 𝑈 𝐴 d i v (𝑣)$ , where $𝑈 𝐴$ is the upset associated to $𝐴$ (all the elements of ${1, \dots, 𝑁}$ that flow down to an element of $𝐴$ ).
  
  Routine Mertens' theorem calculations show that the divergence is positive (more outflow than inflow) for $𝑛 > 𝑁 𝛼 2 + 𝑜 (1)$ and negative (more inflow than outflow) for $𝑛 < 𝑁 𝛼 2 - 𝑜 (1)$ for a certain explicit constant $𝛼 2 = 0.28043830989 \dots$ . From this the optimal $𝐴$ is essentially those elements above $𝑁 𝛼 2$ that flow down to an element below $𝑁 𝛼 2$ . The total outflow $\sum 𝑛 \in 𝐴 1 𝑛$ can then be computed to be $(𝑐 2 + 𝑜 (1)) l o g 𝑁$ for an explicit constant $𝑐 2 = 0.6187712111 \dots$ .
  
  TerenceTao — 22:07 on 23 Apr 2026
  - Thank you for a nice summary in terms of flow networks! I really like the arguments from [1196] and subsequent interpretation in terms of Markov processes, flow networks or zeta process.
    
    Przemek Chojecki — 07:52 on 24 Apr 2026
The result in [Al66] and [ESS68] isn't stated quite correctly here (it would contradict both the example listed later in the commentary, and the sharper result of Chojecki). What they show is that if $𝐴$ is an infinite set with the stated property then $l i m 𝑁 \to \infty 1 l o g 𝑁 \sum 𝑛 \in 𝐴 : 𝑛 \leq 𝑁 1 𝑛 = 0$ , but the convergence is non-uniform in $𝐴$ , and indeed the supremum $s u p 𝐴 1 l o g 𝑁 \sum 𝑛 \in 𝐴 : 𝑛 \leq 𝑁 1 𝑛$ stays bounded away from zero.

TerenceTao — 21:58 on 23 Apr 2026

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.

Log in to add a comment.

Back to the forum

Likes this problem	None
Interested in collaborating	None
Currently working on this problem	None
This problem looks difficult	None
This problem looks tractable	None
The results on this problem could be formalisable	None
I am working on formalising the results on this problem	None