Results regarding the relative-totient function

Question

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)$

Extra

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)$

Answer 1

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

Answer 2

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