Let $p$ be any prime. Let $S$ be the range of natural numbers in $[1, p^2]$.

Suppose that there are no primes in $(p,p^2)$, which means that all prime factors of every number in $S$ must be $p$ or smaller. Equivalently, this means that $\mathrm{gpf}(n)\leq p$ for all $n \in S$, where $\mathrm{gpf}(x)$ is a function which returns the greatest prime factor of $x$.

This means that every number $n \in S$ may be uniquely assigned to a subset $S_k$, such that $\mathrm{gpf}(n)=k$, with prime $k \leq p$.

We start with the straightforward

$$S_p = \{p,2p,3p,\ldots,p(p-2),p(p-1),p^2\}.$$

Note that the mean of $S_p$ is simply its middle term, $\frac{1}{2}p(p+1)$.

The mean value of the elements in $S$ is $\frac{1}{2}(p^2+1)$. Comparing that to the mean value of $S_p$, we see that


This means that our $S_p$ has performed just barely above the aggregate expectation of the average size of elements within a $\mathrm{gpf}$ subset.

I assert that every smaller $S_k$ will have a mean substantially smaller than $S_p$, which effectively means smaller than $S$ too.

Why? I see two reasons:

  1. We've already locked down the best possible number $p^2$, and $p$ on the low end; this means that for any $q<p$, its largest possible value will still be $<p^2$, and its smallest value will be $<p$, meaning that all else being equal, its mean will be accordingly lower.
  2. Much more importantly, $p$ had no interference; every smaller prime will. If e.g. $p=7$, then when we move down to $S_5$, we won't be able to include $5\times 7$, which destroys $S_5$'s mean value. Every smaller prime will find its larger values effectively blocked by the larger primes that came first, preferentially removing larger numbers from their means.

(Maybe worth mentioning that there is also no chance of having that effect work in your favor; if a small prime has a larger prime block it while still early on, it doesn't help. If you get blocked $c$ times before the midway point, you'll get blocked by the same prime either $c$ or $c+1$ times on the second half.)

I think that concludes the nitty gritty part. So...


Since we know that each integer in $S$ will be selected exactly once, it follows that the overall mean of the aggregate of all $S_k$ must equal that of $S$ itself. But if all $S_k$ mean values provide smaller-than-average averages$-$that is, $\bar{S_k}<\bar{S}$ for all $k-$then barring a mistake elsewhere, the pigeonhole principle grants us a contradiction, implying there must be a countervailing amount larger than average that's hasn't been counted. That missing mass, of course, is the contribution of the primes in $(p,p^2)$ that we've ignored.

(And yes, $\bar{S_p}>\bar{S}$, but that amount is always negligible; it's easy to show it's more than offset by $S_2$ alone.)

Toy example

Because I always find plugging in numbers helpful, and perhaps others do too. The numbers are much too small to be compelling, and this is only meant to be illustrative.

  1. Let $p=7$, and so $S=[1,49]$, and $S$ has a mean value of $(1+7^2)/2=25$.
  2. $S_7=\{7,14,21,28,35,42,49\}$. Note the mean value of $S_7$ is $28$.
  3. $S_5 = \{5,10,15,20,25,30,40,45\}$. (Note the missing $35$.) $S_5$ has a mean of $23.75$, which is lower than that of $S$.
  4. $S_3 = \{3,6,9,12,18,24,27,36,48\}$, with a mean of $20.\bar{3}$.
  5. $S_2 = \{2, 4, 8, 16, 32\}$, with a mean of $12.4$.

For the overall average to return to $S$'s $25$, it's clear that some very large terms are required. Therefore, primes.


I would say look at Simpson's paradox, which allows me to accept "all the $S_p<\bar{S}$ except one" without accepting "therefore I need a term $S_p\gg\bar{S}$".

A much bigger hole is that you need weighted averages to combine the $\{S_p\}$ up into $\bar{S}$, and you'll notice that the larger the $p$, the more numbers can land in $S_p$ - they're just $p$-smooth numbers after all.

So your lowest averages are inherently the smallest, least representative sets in the partition.

| cite | improve this answer | |
  • $\begingroup$ I'll check out Simpson's. I'm not sure I understand the weighted averages argumen. In this case, the weights seem immaterial; whether the tiny $S_2$ is weighted as is, or with a relative factor of $100$ relative to the others, it seems like so long as all of the individual $S_k$ are lower than $\bar{S}$, it will require at least one $S_i$ that has a higher mean. One could make a small case for $S_p$ needing a weight, since that's larger than $\bar{S}$, but I don't think that's a problem. But anyway, if all numbers are $<x$, then regardless of weights, they can never exceed $x$, no? $\endgroup$ – Trevor May 24 at 1:30
  • $\begingroup$ Hmm. Yeah, I'm pretty sure I'm right on that. You would need weighted averages to actually combine all $S_k$ properly and have it match $\bar{S}$, but for just using it in the context given to establish the required existence of at least one larger component to a sum, I still think it works. And the p-smoothness is actually what more or less drives things; the whole idea here is to give lie to the alleged ability of small factors to reach anything but a handful of nearby integers, which manifests as these small averages. $\endgroup$ – Trevor May 24 at 3:03
  • $\begingroup$ My point is, didn't you get that $S_p>\bar{S}$ for the original prime $p$? The rest of your argument holds... with $S_p$ being the required higher-than-average prime. $\endgroup$ – obscurans May 24 at 6:09
  • $\begingroup$ That's easy enough to fix. For instance, if you let $n$ be $p^2-1$ instead of $p^2$, that'll do it... the only important values that change are $\bar{S}$ and $S_p$ (all other $S_k$ will stay the same), and they both drop to $\frac{p^2}{2}$, I think. If I've got that right, $S_p$ is no longer higher than the overall mean, and so we lose our one candidate and thus need primes again. $\endgroup$ – Trevor May 24 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.