Relative-totient function (2nd attempt)

Question

Let $\Lambda(x,y)$ be the count of totatives of $x$ that are less than or equal to $y$.

I am asking for the following result to be verified, (particularly the final proposal), I have found no counterexamples and believe the reasoning to be correct.

The first part of this is an interpretation of $\phi(x)$ and the second part uses those observations to construct a formula for $\Lambda(x,y)$.

Let $\phi(x)$ be the number of totatives of a natural number $x$. Euler's product formula for $\phi(x)$ is;

$\phi(x) = x \prod_{p|x}(1-\frac{1}{p})$

This statement can be interpreted as a probabilistic result as follows.

Probabilistic intepretation of $\phi(x)$

Let a $p$-interval be a interval of the form $\lbrace a_{1+kp}, a_{2+kp}, ..., a_{p+kp} \rbrace$ where:

a) $a_i=i$, $\forall i \in \mathbb{N}$

b) $p$ is any prime number, and gives the size of the interval.

c) $k$ can be chosen to position this interval such that it includes any natural number we want.

A $p$-interval is a complete residue class for $p$, which gives rise to the following probabilities:

1. For a randomly selected number $x$ in a $p$-interval, the probability that $x \equiv 0 ($mod $p)$ is $\frac{1}{p}$.

2. For a randomly selected number $x$ in a $p$-interval, the probability that $x \not\equiv 0 ($mod $p)$ is $(1-\frac{1}{p})$.

Another useful property of $p$-intervals is that if we have an interval $I$ of the natural number line, and $I$ is the union of a discrete amount of $p$-intervals for some prime $p$, therefore call $I$ by the new notation $I_p$, then the following probabilities are true.

1. For a randomly selected number $x$ in an interval $I_p$, the probability that $x \equiv 0 ($mod $p)$ is $\frac{1}{p}$.

2. For a randomly selected number $x$ in an interval $I_p$, the probability that $x \not\equiv 0 ($mod $p)$ is $(1-\frac{1}{p})$.

Now consider an interval $I$ that is expressible as both $I_{p_1}$ and $I_{p_2}$

It is easy to show that;

$P(x \not\equiv 0 ($mod $ p_1)$ for $ x\in I) \perp P(x \not\equiv 0 ($mod $ p_2)$ for $ x \in I)$, that is; the two probabilities are independent of each other.

The independence result can be extended to include any number of unique prime numbers, that is; the divisibility of any natural number by a prime number is independent of its divisibility by any other prime number. What this mean in practice is that the probability that a randomly selected number $x$ from an interval $I$, where $I$ is expressable as $I_{p_a}$, $I_{p_b}$, ..., $I_{p_z}$ (So $I$ is the union of a discrete amount of $p$-intervals for each $p=p_a, p_b, ..., p_z$); the probability that $x$ is not equal to $0$ modulo $p_a,p_b,..., p_z$ is just $(1-\frac{1}{p_a}) \times (1-\frac{1}{p_b}) \times$ ... $ \times (1-\frac{1}{p_z})$.

So to conclude, the count of totatives of some $x$ is just $x$ times the probability that a randomly selected number $y\leq x$ is not equal to $0$ modulo any prime divisor of $x$. And this probability is $\prod_{p|x}(1-\frac{1}{p})$.

To summarise Euler's probability, $\prod_{p|x}(1-\frac{1}{p})$ is a result of the following three probabilistic observations:

i) For a randomly selected number $x$ in an interval $I_p$, the probability that $x \not\equiv 0 ($mod $p)$ is $(1-\frac{1}{p})$.

ii) For interval $I$ expressible as both $I_{p_1}$ and $I_{p_2}$, $P(x \not\equiv 0 ($mod $ p_1)$ for $ x\in I) \perp P(x \not\equiv 0 ($mod $ p_2)$ for $ x \in I)$, that is; the two probabilities are independent of each other.

iii) The interval $[1,x]$ is expressible as $I_p$ for all prime divisors of $x$.

When considering $\Lambda(x,y)$, we can build an expression for it that is a result of the three probabilistic observations required to construct Euler's product formula for $\phi(x)$.

Constructing $\Lambda(x,y)$

To construct $\Lambda(x,y)$ let the expected value of $\Lambda(x,y)$ be $\frac{y}{x}\times \phi(x)$. That is;

Let $\Lambda_E(x,y) =\frac{y}{x}\times \phi(x)$

This value may be expected because it is simply the Euler probability for $x$ multiplied by the amount of numbers in the interval $[1,y]$ being $y$. Therefore this expected value relies on the following three conditions:

i) For a randomly selected number $x$ in an interval $I_p$, the probability that $x \not\equiv 0 ($mod $p)$ is $(1-\frac{1}{p})$.

ii) For interval $I$ expressible as both $I_{p_1}$ and $I_{p_2}$, $P(x \not\equiv 0 ($mod $ p_1)$ for $ x\in I) \perp P(x \not\equiv 0 ($mod $ p_2)$ for $ x \in I)$, that is; the two probabilities are independent of each other.

iii) The interval $[1,y]$ is expressable as $I_p$ for all prime divisors of $x$.

Note that the first two conditions are mathematical facts. The third condition is not always true. To refine condition iii) into a statement of mathematical fact about the relationship between a general natural number $y$ and its divisibility by the prime factors of some general number $x$, we would need to find a deeper global statement. If the refined global statement was a statement of equivalence then arguably it will be highly lengthy and chaotic because of the infinitely chaotic distribution of prime numbers to be described in order to scribe the relationship between divisibility properties of general $x$ and $y$. Therefore, we are forced to make use of fuzzier mathematics. Not only that, but until we find deeper global statements that can replace condition iii) then it may be more fruitful to compensate for condition iii) locally; that is in terms of the chosen $x$ and $y$ values, and with functions which cannot yet be generalized and require direct computation. Now less philosophy and more mathematics...

As the third condition is not always true, we expect some degree of variance $V$ such that $\Lambda(x,y) = \Lambda_E(x,y) \pm V$. In order to calculate the variance, we will first make some definitions.

For any natural number $x$, let $x_\flat$ (or $x$ flat) be the product of prime divisors of $x$. Also, let $l_\flat=$gcd$(x_\flat,y_\flat)$ and $x_\sharp = \frac{x_\flat}{l_\flat}$.

This gives us the notation to talk about prime divisors of $x$ which do not divide $y$. These are important for calculating $\Lambda(x,y)$ because the variance $V$ is a consequence of $[1,y]$ not being expressable as $I_p$, where $p$ is any of those prime divisors. Note that:

For each $p$ that divides $x_\sharp$, there exists a $\zeta_p$ such that $p$ divides a natural number in the interval $[y-\zeta_p, y+ \zeta_p]$. Particularly, there exists a natural number in the interval $[y-\zeta_{x_\sharp}, y+ \zeta_{x_\sharp}]$ that is divisible by $x_\sharp$ for some $\zeta_{x_\sharp}$

It is obvious that $\zeta_{x_\sharp} \leq x_\sharp - 1$.

Therefore my proposal is that the variance $V$ belongs in the range $0\leq V \leq \frac{x_\sharp -1}{x_\sharp}\phi(x_\sharp)$. This proposal comes from the fact that we are essentially adding or subtracting totatives of $x_\sharp$ from the interval $[y\pm \zeta_{x_\sharp},y]$ (either + or -, and not caring about the direction of the interval). So

$\Lambda(x,y) = \frac{y}{x}\phi(x) \pm V$ where $0 \leq V \leq \frac{x_\sharp -1}{x_\sharp}\phi(x_\sharp)$

Or more simply; $\Lambda(x,y) = \frac{y}{x}\phi(x) \pm V$ where $0 \leq V \leq \phi(x_\sharp)$

(I believe there is room for improvement).

Answer 1

I will not comment on the soundness of the approach, but I will render a subjective opinion: I don't like it. One of the reasons is that I have found most people do not have a good understanding of probability (I think I have a better than average understanding, but not a good one), and that when one tries such an argument, it is easier to go wrong. It is also easy to go wrong on a combinatorial argument, but it is easier (for me, anyway) to find and point out a flaw in an attempted enumeration, and much of what is expressed above can be rephrased in combinatorial terms, which make a (for me) cleaner and better expression.

Let me reexpress the main points of the post in combinatorial terms:

• For a positive integer $n$ and a positive multiple $m = fn$ of $n$, any interval of $m$ consecutive integers contains $f$ many integers which are multiples of $n$.
• For two positive integers $n, l$, and a positive integer $m$ such that $m$ is a multiple of both $n$ and $l$, any interval of $m$ consecutive integers has $m/n$ multiples of $n$ and $m/l$ multiples of $l$ in it. These latter two sets share some members in common. In particular there are at least $\lfloor m/(n*l) \rfloor $ members which are multiples of $n*l$.
• In the above case where $n$ and $l$ are coprime, there are exactly $m/(n*l)$ members in common.
• What is called Euler's probability can be seen as a version of inclusion-exclusion in the case of more than two numbers (call them $p_i$, with product of $n$) all of which are prime: of the consecutive integers in an interval of length $fn$, $f*(n -\phi(n))$ are not coprime to $n$.
• When $m$ is not of the form $fn$, the counting becomes harder, and different estimates have to be used.

Now the idea of exploring subintervals of certain lengths $y$ in a given interval of length $x$ to get a handle on what is called $\Lambda(x,y)$ in this post is a good avenue, and one that yields some fruit. (See the end of this answer to Part I for more.) I don't like the musical subscripts, so let's dispense with that and consider $x$ and $y$ squarefree for now, and let $l=gcd(x,y)$.

I disagree that the variance $V$ mentioned in the point is a consequence of $y$ not being a multiple of some prime divisors of $x$. The variance is a consequence of many things, and we are challenged to estimate it because (among other reasons) $y$ is (in essence) not a multiple of $x$. In any case, let me use $x$, $y$, and $l=gcd(x,y)$ to rewrite and comment on the next main point of the post:

• For each prime factor $p$ of $x/l$, there is a number $z$ depending on $p$ such that $p$ divides a natural number in $[y-z,y+z]$. (Indeed, if $2z \geq p$ then this follows from earlier bulleted points.) Particularly, for $x/l$ there is a multiple of $x/l$ in the interval $[y-w,y+w]$. (Again, need to choose $w$ big enough: $2w \gt x/l$ works.)

Now the proposal is that the actual number of totatives of $x$ in the interval $[1,y]$ should differ from $y\phi(x)/x$ by an amount that is bounded by $\phi(x/l)$ (perhaps even by the smaller $(1 - l/x)\phi(x/l)$). This is a interesting conjecture.

However, the question asks: is the reasoning sound? The answer is that there is a proposal on the table, and no reasoning to support the proposal. There is a probabilistic argument for the situation $y=x$, but it is not clear that such an argument works at all for $y$ not a multiple of $x$. One has to try an argument based on $y$ not being $x$, and one of the main assumptions that was carried before (that every prime factor of $x$ is a factor of $y$) is missing. The words before that do not support the case being considered, as far as I can see.

To attempt to refute such a conjecture, one needs to pick $x$ and $y$ such that the purported error $\phi(x/\gcd(x,y))$ is smaller than known bounds on the error. Since such bounds are asymptotically smaller than any fractional power of $x$, one needs $y$ to share all but a few prime factors with $x$, so the applicability of this conjecture (if true) will be limited to those few choices of $y$ for which $\phi(x/gcd(x,y))$ is small. As an example, if $x$ is the product of all primes at most 100, $\phi(x/gcd(x,y))$ will need to be less than $2^{24}$, meaning $y$ will have to share at least 16 of the 25 prime factors of $x$. We already have some results of Lehmer which show that $V=0$ for $x/y$ a divisor of $p-1$ for $p$ one of the larger prime factors of $x$, so you won't be able to choose really large values of $y$ to test the conjecture for this particular $x$.

I recommend numerical computation on small examples to see where this fails. At present, there is no reasoning presented to overcome the difficulty noted, that $y$ is not a multiple of $x$. After the case of squarefree $x$ has been handled, you can easily handle the case of nonsquarefree $x$.

Gerhard "Sorry, It's Not A Proof" Paseman, 2015.10.01

Answer 2

As I pointed out in my comment, $\Lambda(x,y) = y\phi(x)/x + O(x^{\epsilon})$. Apply this to $x_{\flat}$ instead of $x$ to get $\Lambda(x_{\flat},y) = y\phi(x_{\flat})/x_{\flat} + O(x_{\flat}^{\epsilon})$.

Note that $\Lambda(x,y) = \Lambda(x_{\flat},y)$ and that $\phi(x_{\flat})/x_{\flat} =\phi(x)/x$, so $\Lambda(x,y) = y\phi(x)/x + O(x_{\flat}^{\epsilon})$.

Now $x_{\flat} \phi(x)/x = x_{\flat}\phi(x_{\flat})/x_{\flat} \ge x_{\flat}^{\epsilon}$, for suitably small $\epsilon$. This proves your "proposal" with $x_{\flat}$ instead of $x_{\sharp}$. They agree if $gcd(x,y)=1$. Note that what you call $x_{\sharp}$ depends also on $y$.