4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note a corollary to this claim is that if we let $\Lambda_\chi(x,I)$ be the number of totatives of $x$ on the interval of natural numbers $I$. If $I$ is of the form $\lbrace a_{1+ky}, a_{2+ky}, ..., a_{y+ky} \rbrace$ with $a_{y+ky} \leq x$ then $\Lambda_\chi(x,I) = \frac{n}{x} \phi(x) \pm V$, where the variance $ 0 \leq V \leq \frac{x_\# -1}{x} \phi(x)$ $\endgroup$ – Brad Graham Sep 24 '15 at 20:41
  • $\begingroup$ This needs a lot of cleanup. You need to resolve occurrences of n,x, and y. My guess is that wherever you have n you mean one of x or y instead. Also, you need to say lambda(x,y) means count of totatives of x in interval (0,y], or whatever it is you mean. Finally, test it by choosing y so that x_sharp is small, and see if you can break your claim. Gerhard "So Practice What I Preach" Paseman, 2015.09.24 $\endgroup$ – Gerhard Paseman Sep 24 '15 at 20:59
  • $\begingroup$ @Gerhard Thanks, you are right, so the notation has been cleaned. Well $\frac{\phi(x)}{x} = \prod\frac{ p-1}{p}$ so if $x_\# -1 \geq 2$ the variance interval includes at least one natural number. So to try and break the claim we can consider $x_\#=2$. Let $x=6$, $y=3$ therefore $x_\# =2$. $\Lambda_E(6,3)=1$ and the variance is less than $1$... Now I'm stumped, because I can't see what could be wrong except that I could have misinterpreted my second to last highlighted point. $\endgroup$ – Brad Graham Sep 24 '15 at 21:43
  • $\begingroup$ Forget the last comment... $\Lambda(6,3)$ should be $1$ (!) $\endgroup$ – Brad Graham Sep 24 '15 at 21:56
  • 1
    $\begingroup$ I concur with Felipe. Much as I am interested in the topic, there are cases that can be used to test such conjectures. In particular, the Lehmer paper and Aaron Meyerowitz's question (88777) and answer show a worst case scenario: for a product x of k primes of the form (mt - 1) a y near x/m produces an error of near 2^{k-1}. You can do this testing and some additional research on your own for a while. Leave editing the question alone for a week or more until you have a significant idea to add/take away. Gerhard "Resist The Temptation Of Tweaking" Paseman, 2015.09.25 $\endgroup$ – Gerhard Paseman Sep 25 '15 at 16:06
3
+25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Okay, cheers Gerhard. I should try it for more values of $x,y$ but have yet to find a counter example. If anybody finds a counter example, that would be amazing thanks. Ps what other variables could contribute to the variance??? It seems to me that we cannot produce the same construction for $y\neq x$, nonetheless we can atleast try to account for the differences between the $x=y$ and $x\neq y$ cases, using a sort of fuzzy-surgical approach as i tried. Perhaps we can prove a model is sound by exhausting all constructed variables which are holographic to compositions of cognitive mechanisms..? $\endgroup$ – Brad Graham Oct 1 '15 at 20:37
  • $\begingroup$ Of course I have no idea how we could do that, but hypothetically I mean. Perhaps we could do it in the near future, especially with contemporary research in cognitive-decision theory.. Anyways. Tasks: find a counter example or prove the conjecture in an alternative way, disregarding the soundness of the model until further philosophical investigation. $\endgroup$ – Brad Graham Oct 1 '15 at 20:42
  • $\begingroup$ I think the last point to made is that; the variance is definately due to those prime factors of $x$ coprime to $y$ and heres why. For each shared prime factor $p_i$, there is exactly $x/p_i$ of them in $[1,x]$ and $y/p_i$ of them in $[1,y]$. So the amount of numbers not divisible by $p_i$ in $[1,y]$ is exactly $y/x \times (p_i-1)/p$. So we have a fraction (expressable as a partial Euler probability) of $[1,y] $ which are totatives to all shared prime factors of $x$ and $y$. Hence the variation is an expression of those primes not shared. $\endgroup$ – Brad Graham Oct 1 '15 at 23:33
  • $\begingroup$ And as $\phi(x)$ is also the amount of totatives of $x$ in an interval $[nx, (n+1)x]$ due to periodicity of increasing natural numbers modulo primes, we get the expression $\phi(x_\sharp)$ $\endgroup$ – Brad Graham Oct 1 '15 at 23:37
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks a lot Felipe, can anything be said of the count of totatives of $x$ in some interval $I$ with length $y$, is it also known to be $y\phi(x)/x + O(x^{\epsilon})$? $\endgroup$ – Brad Graham Sep 24 '15 at 22:47
  • $\begingroup$ And lastly, is there an interpretation of $\Lambda(x,y)$ in terms of $\phi(y)$? $\endgroup$ – Brad Graham Sep 24 '15 at 22:56
  • 2
    $\begingroup$ @BradGraham About your questions in the comments, I don't know. You should check out Hardy and Wright. It has a lot of information. $\endgroup$ – Felipe Voloch Sep 24 '15 at 23:15
  • $\begingroup$ Unfortunately I can't accept this answer; it is supposedly a proof, yet you found a counter example, so it can't be a proof $\endgroup$ – Brad Graham Sep 25 '15 at 17:26
  • $\begingroup$ It's a proof of a weaker statement from the one in a previous version of this question, in which one takes $x_{\sharp}$, in place of $x_{\flat}$. The version with $x_{\flat}$ is false due to the counterexample. I guess this resolves the earlier version. I haven't really looked at the current version, so I have nothing to say there. As far as accepting the answer, it's entirely up to you. $\endgroup$ – Felipe Voloch Sep 25 '15 at 17:40

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.