11
$\begingroup$

Does anyone know how to estimate (as $n$ tends to infinity) the number of solutions of

$$n=x+y+z$$

where $x,y,z$ are positive integers with $x$ coprime to $y$ and to $z$?

Computer experiments suggest that there are roughly $cn^2$ solutions, where $c>0$ is an absolute constant.

Improve this question
$\endgroup$
5
  • $\begingroup$ Here's an approach. Pick distinct primes p and q. Calculate T(n), the number of numbers x less than n whose prime factors are either p or q. For each such x, consider how many decompositions of n- x have both parts coprime to pq. After summing over enough pairs p < q, you should get a lower bound for c. As an upperbound, it may be enough to argue by parity for a good (not great) upper bound. Gerhard "Ask Me About System Design" Paseman, 2011.04.13 $\endgroup$
    – Gerhard Paseman
    Commented Apr 14, 2011 at 3:18
  • 2
    $\begingroup$ I just did a computer experiment for $n$ near $1000$ and $2000$. It looks like it varies between $0.15n^2$ and $0.3n^2$ but was oscillating between these two bounds (actually alternating for $n$ odd and even) and it didn't look like you'd get $cn^2$ like you suggested. How far did you compute? $\endgroup$
    – Felipe Voloch
    Commented Apr 14, 2011 at 4:08
  • $\begingroup$ It may help to notice that the number of pairs in question is half the number of pairs $(z,u)$ with $1\le z,u\le n$ such that $(z,u)=(n-z,n-u)=1$. $\endgroup$
    – Seva
    Commented Apr 14, 2011 at 10:43
  • $\begingroup$ Felipe: I know that sometimes when I do quick computer experiments I get lazy and try, say, n equal to powers of two or powers of ten. Perhaps Daniela only tried even numbers? $\endgroup$
    – Michael Lugo
    Commented Apr 14, 2011 at 21:50
  • $\begingroup$ Thanks for the comment on using $x$ of the form $pq$ for distinct primes $p$ and $q$. Unfortunately, I really need to prove a lower bound of the form $c^2 n$ and with the method suggested I can only get $c n^2/\log\log n$. Yes, the number of solutions (again computationally) seems to depend on the fact that $n$ is even or $n$ is odd. (thanks for pointing this out to everybody). "Luckily" I only need to prove that the number of solutions is at lest $cn^2$ for some absolute constant $c$. $\endgroup$
    – Daniela
    Commented Apr 15, 2011 at 1:32

3 Answers 3

Reset to default
6
$\begingroup$

For $n$ prime my heuristics tells me that $c=\frac{1}{2}\prod_p\left(1-\frac{2}{p^2}\right)$, the product being over all primes. Is this supported by computer experiments? If yes, I will share more details.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, for $n=p$ with $p$ prime your product is very close. For $n=2p$ it's larger by about $3/2$, for $n=3p$ by $8/7$, for $n=4p$ by $3/2$ again, for $n=5p$ by $24/23$, for $n=6p$ by $3/2\times8/7$. So based on the empirical evidence I'll conjecture $\frac{1}{2}\prod (1-1/p^2) \prod (1-2/q^2)$ over primes $p$ that divide $n$ and primes $q$ that don't. I don't have analysis to support it, but I look forward to your details. $\endgroup$
    – Zander
    Commented Apr 15, 2011 at 0:53
  • 1
    $\begingroup$ This is great! Using this comment and the remark below it I managed to prove the suggested "conjecture". Thanks!!!! $\endgroup$
    – Daniela
    Commented Apr 15, 2011 at 4:32
3
$\begingroup$

If $x$, $y$ and $z$ are chosen "randomly" subject to $x$ and $y$ not both even and $x$ and $z$ not both even, the probability that $x+y+z$ is even is $3/5$. So it's not surprising that you get different results for odd and even $n$.
Similarly, there should be effects depending on whether $n$ is divisible by each prime: given that $x$ is coprime to $y$ and to $z$ the probability that $x+y+z$ is divisible by $p$ should be $\frac{p^2-1}{p^3 - 2 p + 1}$.

Improve this answer
$\endgroup$
3
$\begingroup$

The number of solutions is bounded from below by $cn^2$ (and from above too by obvious reasons). Indeed, let's choose odd $x$ and $y$ at random and independently from the segment $[1,2N]$ for $N$ about $n/100$ and put $z=n-x-y$. For any $d$, the probability that both $x$, $y$ are divisible by $d$ is at most $N^{-2}(N/d+2)^2=d^{-2}+4/Nd+4N^{-2}$. Analogously for $x$ and $z$. Summation over all $d=3,5,7,\dots,n$ gives the upper bound for the probability of at least one event of the form $2(1/9+1/25+\dots)+o(1)$. This is less then $0.8$, so with the probability at least $0.2$ both pairs $(x,y)$ and $(x,z)$ are coprime.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks this is a very simply and slick argument. But there is something I don't understand. Unfortunately, the part of the argument I do not agree with is when you choose randomly $x$ and $z$ (you say "analogously for $x$ and $z$"). In fact, it looks to me that I cannot do that. Once $x$ and $y$ are choosen $z$ is uniquely determined. For all I know, if I compute the probability of $x_1$ and $y$ coprime in $[1..2N]$ and $x_2$ and $z$ coprime (with $x_2$ in $[1..2N]$ and $z$ in $[1..n]$), it could happen that the probability that I find simultaneously $x$, $y$ and $z$ with $x+y+z=n$ is $0$. $\endgroup$
    – Daniela
    Commented Apr 15, 2011 at 1:44
  • $\begingroup$ Yes, $z$ is uniquely determined, but when does $d$ divide both $x$ and $z$? When $x$ is divisible by $d$, and $y$ is congruent to $n$ modulo $d$. The number of odd integers from 1 to $2N$ with prescribed remainder modulo $d$ does not exceed $N/d+2$, I hope so:) $\endgroup$
    – Fedor Petrov
    Commented Apr 15, 2011 at 4:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .