I thought the following fact was trivial, but could not find a proof anywhere. The proportion of integers with an odd number of distinct prime factors seems to be 1/2 as you would expect, but it looks like this apparently trivial result hasn't been proved so far (so I suppose it must be a conjecture.)

You get a $1 million award if you solve any of these conjectures

Starting points to answer this question, are this link and this one. It seems that this proportion is always below 1/2 but nevertheless converging to 1/2 -- see here for more details. Would love to hear more about this.

A generalization of this problem is as follows: what is the proportion of polynomials that have an odd number of distinct roots? You can even replace polynomials by real-valued functions that have a Taylor series expansion and a finite number of roots, as they can be approximated arbitrarily closely by polynomials. You would expect the answer to also be 1/2, yet it is not easy to build a probability space on the set of real-valued functions. Even for the set of integers, it is not that simple, thought it can be done using the theory of stochastic point processes. Now If you include functions that have an infinite number of roots, such as the sine function, you are opening up a new can of worms: are these functions rare enough that their density, among all functions, is zero?

To answer the previous question, a first step is to determine how frequently a random walk (Markov chain) or Brownian motion crosses the X-axis infinitely often. Or better, look at integrated Brownian motions (see chapter 2 in my book) as they are everywhere differentiable. The answer is that these one-dimensional perfectly random processes always cross the X-axis infinitely many times, see here (in short they come back to the origin infinitely many times if dimension is one or two); less random processes may not have this feature, but they represent a tiny fraction of stochastic processes, just like numbers with a distribution of digits that is different from uniform, represent a tiny fraction of all numbers, so small that their density (Lebesgue measure) is zero. But you could say the same thing about continuous functions: they represent a tiny fraction of all functions.


  1. By integers with an odd number of distinct prime factors, I mean, for instance, that the number 2 * 2 * 2 * 5 * 7 * 7 has three distinct prime factors: 2, 5 and 7.
  2. Perfectly random processes are more numerous than those that are less random, because at any time, a perfectly random process can move arbitrarily in any direction (up or down) by any random increment, while less random processes have these moves somewhat constrained.

Other great conjectures that I love

  • The digits of Pi are uniformly distributed, in any base. More on this here
  • If two positive real numbers x and y have INT(2*FRACT(kx)) =  INT(2*FRACT(ky)) for all positive integers k, then x = y. Here INT is the integer part function, and FRACT is the fractional part function. 

Related articles

For related articles from the same author, click here or visit www.VincentGranville.com. Follow me on on LinkedIn, or visit my old web page here.

Views: 1380

Reply to This

Replies to This Discussion

A reader posted the following, see below. So this is not new, it is actually related to the Pólya conjecture.

I believe this fact follows from some upper bounds on the Mertens function.

Assuming the conjecture is referring to the limiting natural density, then it suffices to show that the Mobius function is -1 and 1 with limiting proportion 1; this entails the desired result over squarefree integers (which are of positive density in the naturals). Then if we go up to N large enough, we can just apply this limit recursively on N/4 (for squarefree integers times 4), N/9, N/16, etc. and get a ratio within epsilon 1/2 for arbitrarily small epsilon.

But showing that the Mobius function is equally often 1 and -1 just amounts to saying the Mertens function (defined to be the partial sums of the Mobius function) divided by the number of squarefree integers less than n goes to 0, which is equivalent to saying |M(x)| = o(x). But we have the bound |M(x)|<0.58782x/log^(11/9)(x) for x>685 due to Kotnik. (Note that assuming the Riemann Hypothesis, we can get down to x^(1/2 + e), but we don't need anything that strong.)

Edit: Forgot my relevant number theory functions for a second, I was trying to describe the Liouville function.

Related trivia: The smallest integer at which there are more integers with an even number of prime factors than an odd number is 906150257, which is a counterexample to the Pólya conjecture.


© 2021   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service