Let $\Lambda(x,n)$ be the the number of totatives of $x$ which are less than or equal to $n$, and $\Phi(x)$ be Euler's totient function.

For now assume $x>n$.

Is there a general formula for $\Lambda(x,n)$? Furthermore, has the result stated below been documented elsewhere?

Let $l = gcd(x,n)$, $x'= x/l$ and $n'=n/l$

I have a wrong (24.09.15) proof that...

$\Lambda(x,n) = \frac{n'}{x'} \Phi(x) \pm V$, where the variance $ 0 \leq V \leq \frac{x'-n'}{x'n'} \Phi(x)$


Actually from what I can gather this result can be generalized further as follows:

Let $\alpha_{n,k}$ be the interval $ \lbrace a_{0+nk}, a_{1+nk}, ..., a_{(n-1)+nk} \rbrace$ where;

a) $k$ is some natural number such that we can choose its value to position this interval somewhere on the non-negative integer line,

b) $a_i=i$ for all non-negative integers $i$

c) $n$ is a natural number, that we can chose as the size of this interval. (Notice this interval always starts with a number divisible by $n$.)

And, let $\Lambda_\chi(x,I)$ be the number of totatives of $x$ on the interval of non-negative numbers $I$.

For any $n$ and $x$ such that $n<x$, if we choose a $k$ such that $a_{(n-1)+nk}\leq x$ then;

$\Lambda_\chi(x,\alpha_{n,k}) = \frac{n'}{x'} \Phi(x) \pm V$, where the variance $ 0 \leq V \leq \frac{x'-n'}{x'n'} \Phi(x)$


As I understand the claim $\Lambda(x,n) = \frac{n'}{x'} \Phi(x) \pm V$, it is false for some $n$ and $x$ with $n$ close to $x$. Let us take $x$ to be $P_4=210$, the fourth primorial. Let us take $n$ close to and less than $210$, say $208$. (I use Gerry's observation that $n'/x' = n/x$.) The claim says that the number of totatives of $210$ which are less than or equal $208$ is close to the expected number, with an error $V$ bounded by $\frac{x' -n'}{x'n'}$ times the expected value. For $x=210$ the expected value is $48$, and so the number of totatives given by the formula is in the range (my interpretation of $=$) $(208/210)*48 \pm 48*(2/(208*210))$, which I rewrite as $48 - 16/35 \pm 1/455$. (See comment below for the missing factor.) The allowed range does not even contain an integer, much less the correct answer which is 47. For the same $x$, one can find further $n$ which violate the claim.

One should note that $\Lambda(x,n) + \Lambda(x, x-n) = \Phi(x)$, and that the error for an interval of length $n$ should be the same (up to sign) as the error for length $x-n$. The current estimate does not show such a symmetry.

In an earlier question I referenced D. Lehmer's 1955 work on "Distribution of Totatives". One of his results there I can provide here with a hint of proof. Take a large squarefree integer $x$ with a prime factor $p$ of $x$, and assume $x \gt p$. The range of totatives of $x$ in $(0,x)$ is like $p$ copies of the range of totatives of $n= x/p$ concatenated together, with one copy dilated by $p$ subtracted off. If you look at the interval $(0,x/(p-1))$ and count totatives of $x$, you get $p/(p-1)$ many totatives of $n$ [actually, the totatives of $n$ in the interval $(0,n(p/(p-1)))$ ] minus $1/(p-1)$ of the scaled copy of totatives of $n$, which is in 1-1 correspondence with the totatives of n in $(n,n(p/(p-1)))$. So the number of totatives of $x$ in $(0, x/(p-1))$ is the same as the number of totatives of $n$ in $(0,n)$, which is $1/(p-1)$ times the number of totatives of $x$ in $(0,x)$.

Thus one of Lehmer's results in the article implies that for any prime factor $p$ of $x$, the interval of length $x/(p-1)$ beginning at 0 contains exactly the expected number of totatives. Further, this argument holds for other integers $j$ and intervals $(jx/(p-1), (j+1)x/(p-1))$. So there are some intervals for which it can be easily shown that $V=0$. If $x$ is divisible by the square of a prime $p$, it is easy to see that $(jx/p, (j+1)x/p)$ contains the expected number of totatives as well.

For more general intervals that do not have $x/p$ or $x/(p-1)$ or some multiple of such as endpoints, one can still get some modest results. As pointed to in this question, if $x$ is squarefree with $k$ distinct prime factors, an interval of the form $(0,n]$ has as many totatives of $x$ as the expected number plus or minus an error bounded by $2^{k-1}$. We can concatenate errors to say the same for an interval $(m,n]$, but with error bounded by $2^k$.

I have not seen published anywhere the following, and would appreciate references. Let $x$ be squarefree with $k \gt 2$ prime factors, and $p,q$ distinct primes dividing $x$. Let $n$ be an arbitrary real. The number of totatives of $x$ in the interval $(n, n+L]$ is different from the expected number by at most a) $2^{k-1}$ if $L= x/p$ or $x/q$, b) $3(2^{k-2})$ if $L=x/(pq)$. (One can extend this to larger sets of primes and smaller versions of $L$, but not with satisfactory results.) Unfortunately this does not mean that smaller length intervals yield smaller deviations from the expected value.

Gerhard "Been Thinking Lots About This" Paseman, 2015.09.23

  • $\begingroup$ I made a mistake: $\frac{x'-n'}{x'n'}$ differs from the result I use by a factor of 2 for my choices of $x$ and $n$. However, the result when corrected still shows no integer in the range, and the claim is still false. Gerhard "Correct Up To Small Error" Paseman, 2015.09.23 $\endgroup$ – Gerhard Paseman Sep 24 '15 at 2:57
  • $\begingroup$ For $x=210$ and $n=208$, $gcd(x,n)=2$, $x'=105$ and $n'=104$. So $V \in [0,e]$ where $e$ is very small. But we need $\Lambda(x,n)=47$ which the formula doesn't give. Hmmm. Ps typing from phone hence premature comment. $\endgroup$ – Brad Graham Sep 24 '15 at 3:06
  • $\begingroup$ Ps i have a feeling my results works for $x,n$ squarefree - whose example my result was extrapolated from. I need to think more carefully about non-squarefree numbers. $\endgroup$ – Brad Graham Sep 24 '15 at 3:12
  • 2
    $\begingroup$ If you choose x to be a larger primorial, you can get n (say n+6=x) not far from x to be squarefree, and you will run into the same problem again. I suggest you look through your proof and use these choices of x and n to find where the proof breaks. Gerhard "Always, Always Use Test Cases" Paseman, 2015.09.23 $\endgroup$ – Gerhard Paseman Sep 24 '15 at 3:17

Although this is really a comment, I decided it was important enough to post as an answer.

Having studied the problem posted above, I was suspicious of the given claim because of symmetry reasons. It seemed that for n far away from x the variance quantity was large enough as to render the estimate unuseful, where as for n close to x, the variance quantity could get quite small, when in reality the error should be the same. So my experience guided my "attack" on the claim.

Even without this experience though, it should be clear how to test the claim: if n is close to x, n' is close to x' and the claim then predicts a small variance for the estimate of the number of totatives. If a claim predicts a strong result, test it with numbers that might provide such a strong result. I did that, and broke the claim.

As mentioned in another comment, this is a good strategy for testing a proof: when you think you have one, specialize it to challenge numbers ($x=210, n=208$ in my example), and go through each step of the proof with these challenge numbers. At some point, a statement made in the proof will be falsified with the challenge. If this occurs early in the proof, you have at least two options: give up, or rearrange the proof to make a different proof with the faulty claim near the very end. If this occurs late, see if you can rearrange the proof to push the faulty statement as near to the end as you can.

Why do this? Isn't this going to end up with another faulty proof?

The point is to develop and test an idea. A good proof depends on one (perhaps more than one) basic idea which is true, and support structure to apply this idea to yield a true theorem. However, the idea may be useful in other contexts. The technique of pushing away (or even replacing) faulty statements that don't support the idea has the goal of refining and developing the idea, which may be good but misplaced (the idea may work in a different proof of a different theorem).

The test cases help you find and clear away the garbage detracting from the idea, but if the idea is worth preserving, you need to do the work of garbage collection and maintenance to take the idea as far as it can go with the present proof, or else decide the idea is in the wrong proof.

Gerhard "Talking My Kind of Metamathematics" Paseman, 2015.09.24


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.