Mathematicians Outwit Hidden Number Conspiracy

[ximeng]

This is a great overview, but there is a big gap between the narrative style overview here and the technical details of the proof in the paper. The conclusion is in very vague terms ("far fewer integers"):

Helfgott and Radziwiłł’s solution to the logarithmic Chowla conjecture marked a significant quantitative improvement on Tao’s result. They could sample over far fewer integers to arrive at the same outcome: The parity of the number of prime factors of an integer is not correlated with that of its neighbors.

It would be really interesting to have a commentary to go along with the proof to help bridge this gap. This could explain why choices are made in the proof and help to visualise the implications.

This article comes close in some ways, for example with the examples regarding multiplicativity of the Liouville function. OK, it is a 100 page paper, so understanding the details of the proof is going to be tough. It would still be fun if there was a way as an interested reader to step up from reading this type of article to at least understanding the abstract of the paper.

[CaptainNegative]

The article goes into significantly more depth than is quoted above, building motivation first by describing the approach initially taken by Tao (as I understand it, analyzing the combinatorial expansion of a particular graph on the integers) followed by giving an overview of the new approach (analyzing the spectral expansion of the difference between Tao's graph and a simplification thereof) and why the simplification was reasonable. Obviously the overwhelming majority of the gory details were spared, but given the content I thought the author did a good job giving a high level picture accessible to a relatively general audience.

[hardlianotion]

There is a rather interesting exposition paper put out yesterday by Helfgott: "EXPANSION, DIVISIBILITY AND PARITY: AN EXPLANATION" https://arxiv.org/pdf/2201.00799.pdf

Have only scanned it, but it seems well motivated and readable.

[WoahNoun]

>an interested reader to step up from reading this type of article to at least understanding the abstract of the paper.

I don't think this is a reasonable expectation for most modern results in mathematics. There is just too much background to cover. Quanta's narrative style is the absolute best at it, but often leaves people with technical backgrounds outside of math wanting more. But I don't really think that's possible.

[ffhhj]

Assume n>1 . How can I prove one can only find 23 primes or less in the interval from 10n to 100+10n?

[librexpr]

I'm just an amateur, but if you don't mind some brute-forcing, it's enough to prove that for every n between 1 and (2*3*5*7*11*13)/10+1=3004, exclusive of 1 but inclusive of 3004, there are at most 23 numbers between 10n and 100+10n which are not divisible by any of P={2, 3, 5, 7, 11, or 13}. Let's call numbers which are not divisible by P "potential primes". Every prime greater than 13 is a potential prime but not vice-versa.

This obviously works for the n we check manually because if there are at most 23 potential primes, there are at most 23 primes.

This also works for n greater than those we check manually, because potential primes in this set "loop" when you get past 30030. Because 30030 is divisible by every prime in P, for any x which is divisible by P, 30030 + x will also be divisible by P. Similarly, if x is a potential prime, 30030 + x will also be a potential prime. This means that there are all the same potential primes from 0 to 30030 as there are from 30030 to 30030*2, and from 30030*2 to 30030*3, and so on. Since by brute force, there was always at most 23 potential primes in the first loop (plus the beginning of the second loop, to make up for the fact that we start at n=2), then it must be true in every later loop.

Here is code that does the brute force in ruby 3, finishing the proof:

  require 'prime'
  
  def get_cycle_extended(n)
    # Get every "potential prime"
    primes = Prime.each(n).to_a
    cycle = []
    for i in 0...(primes.reduce(:*) + 200) # + 200 to be safe
      is_eliminated = false
      for prime in primes
        if i % prime == 0
          is_eliminated = true
          break
        end
      end
      cycle << i if not is_eliminated
    end
    cycle
  end
  
  p get_cycle_extended(5) # just checking that get_cycle makes sense
  
  size = 13
  cycle = get_cycle_extended(size)
  
  for n in 2..3004
    s = 10*n
    e = 100 + s
    restricted = cycle.filter { |x| (s..e).include?(x) }
    if restricted.length > 23
      raise "false at #{n}"
    else
      p restricted
    end
  end

Edit: Since I posted about copyright not long before posting this, I'll just go and say explicitly that I'm releasing this comment to the public domain using CC0.

[raverbashing]

Since your interval begins at a divisible by 10 boundary, this makes things easier

If you think only about the numbers divisible by 2, 3, 5 you'll get a result pretty close to 23 (21 actually). But you can elaborate the proof to get to a closer number

(just remember that after you take 100/2 and 100/3 you need to add back 100/6 which are the ones you counted twice and so on)

[gizmo686]

I think this can be done in a straight-forward brute force manner.

Consider the first 7 primes [2,3,5,7,11,13,17]. Each of these primes defines a "sieves", that can be used to filter out multiples of it. For instance, 2 defines the sieve [0,2,4,6,...] while 17 defines the sieve [0,17,34,...].

Instead of infinite sieves, consider only the finite sieves that go up to 100. for instance, 17 would give the sieve [0,17,34,...,85]. Over any interval of 100 integers, all multiples of p can be filtered out by filtering out the contents of p's finite sieve with some constant offset (<p).

For instance, on the interval [0,100), we can filter out all multiples of 3 by filtering out the sieve [0,3,6,...,99]. Similarly, on the interval [10,110), we can filter out the multiples of 3 using the sieve [2,5,8,...98].

The notation here is a bit backward, but makes sense if you think of the sieve as a bit-field with 100 elements labeled 0 to 99. The sieve [2,5,8,...98] then represents the bitfield where every third element is true, starting with the second element.

As a notional shorthand, we can represent this sieve as [3]+2, to represent all multiples of 3, with an offset of 2 (within the range [0,100). Formally speaking: [p]+k = [p * n + k | for integers n,k where 0 <= p * n + k < 100]

For sieves X,Y define X | Y to be the union of X and Y. Under the bitfield interpenetration, a bit in X | Y is set if it is set in either X or Y.

For every range of 100 integers, there exists a sieve that filters out all multiples of both p and q. This sieve takes the form: [p] + k | [q] + m.

We can further restrict 0<=k<p and 0<=m<q.

Note that there are only finitely many such sieves. Over any sequence of 100 integers, one of those finitely many sieves will filter out all multiples of p and q.

This approach can be extend to any number of primes.

Construct all such sieves for the primes [2,3,5,7,11,13,17]. For each sieve, count how many elements it allows through, and find the sieve which allows the fewest elements through. This is an upper bound of the number of integers within a range of 100 that are not a multiple of the first 7 primes. Assuming your range of integers starts at at least 18, this is an upper bound on the number of primes it can have.

In python:

    primes=[2,3,5,7,11,13,17]
    sieves=[set()]
    for p in primes:
        newSieves=[]
        for k in range(0,p):
            toAppend = set([ k + pp for pp in range(0,100,p) if k + pp <= 100])
            for sieve in sieves:
                newSieves.append(sieve | toAppend)
        sieves = newSieves

        print "\n{}:".format(p)
        print 100-min([len(s) for s in sieves])

[asteroidbelt]

I would not click the link if not "conspiracy" in the title.