1
$\begingroup$

Let $n \in \Bbb N$ and $k \in [n]$, where $[n]=\{1,...,n\}$. I want to show:

The number of solutions $(x,y,z)$ of the equation $x+2y+3z = 2n+k$ where $x,y,z \in [n]$ is at least $cn^2$, for some constant $c$ that is independent of $n$ and $k$.

Sidenotes:

  • The $2n$ term is not important to me and can be replaced by any term that depends only on $n$, if such a $c>0$ exists. for $2n$ it seems to exist.

  • My aim is to show the same for general $r$ with the equation $x_1+2x_2+3x_3+...+rx_r=k+(r-1)n$ and $c$ a function of $r$ only.

In the case $r=2$ we see that $x+2y=n+k$ has at least $\lfloor\frac n2 \rfloor$ solutions, so we can take $c=\frac 13$. This is since if we start increasing $y$ then at $y=\lceil \frac k2 \rceil$ we will have a solution and then we will have a solution for $x$ in the next $\lfloor \frac n 2 \rfloor $ values of $y$. Geometrically this is a line that has a lattice point once in every two points.

This reasoning is less clear in the case $r=3$, looking at the possible solutions of $x,y$ as we increase $z$.

UPDATE

Experimenting using Python shows that for $r=3$ the number of solutions converges to $\frac 14 n^2$. It is enough to prove that there is such a constant $c$ for all large enough $n$, since then we can make $c$ smaller so that it will work for the small values of $n$ as well. The natural guesses that the number of solutions is at least $\lfloor \frac {n^2} 4 \rfloor$ or at least $\lfloor\frac n2\rfloor ^2$ are both sometimes false, though.

The script, in case anyone wants to experiment too:

from itertools import product

def number_of_solutions(n, k, r):
    return sum(1 for variables in product(range(1, n + 1), repeat=r-1) if
               (r - 1) * n + k - sum((k+2)*variables[k] for k in range(len(variables)))
       in range(1, n + 1))

def minimal_number_of_solutions_over_all_k(n, r):
    return min([number_of_solutions(n, k, r) for k in range(1, n + 1)])

def find_approximated_c(r):
    for n in range(2, 1000):
        approximated_c = minimal_number_of_solutions_over_all_k(n,r) / (n ** (r - 1))
        print(n, approximated_c)  # stabilizes on 0.25 when r=3
$\endgroup$
0
$\begingroup$

Since you are looking for "at least" then its obvious that $2n+k$ have less solutions when $k=1$ than when $k$ is very big or $k=n$ (because the partitions of a number grows exponentially), so we are left with $x+2y+3z = 2n+1$ in order to give the "at least" constant $c$.

Now $z$ can run from $1$ up to $\lfloor \frac{2n+1}{3} \rfloor$.

Now we are left with $x+2y = 2n+1-3z$ such that $z$ runs form $1$ up to $\lfloor \frac{2n+1}{3} \rfloor$.

Let $m=2n+1-3z$ so $x+2y=m$ , in how many ways we can write some integer $m$ as sum of $x+2y$ , its easy to see that when we give $y$ a fixed value, $x$ is forced into a fixed value also, so we have $\lfloor \frac{m}{2} \rfloor$ solutions.

So we arrive at this sum $\sum \limits_{z=1}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{m}{2} \rfloor = \sum \limits_{z=1}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor $.

But there is a catch in these solutions, in these solutions i made sure that $1 \leq y,z \leq n$ but not for $x$ so for some solutions $x$ could equal $0$ or $x >n$.

To correct this let $x =2n+1-3z-2y \leq n$ which means $3z+2y \geq n+1$ which means that $y \geq \frac{n+1-3z}{2}$ which means that $y \geq \lceil \frac{n+1-3z}{2} \rceil$ (solution which will be subtracted each time). until we reach that $\lceil \frac{n+1-3z}{2} \rceil < 1$

So Approximately we get this summation $\sum \limits_{z=1}^{\lfloor \frac{n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor - \lceil \frac{n+1-3z}{2} \rceil + \sum \limits_{z=1+\lfloor \frac{n+1}{3} \rfloor}^{\lfloor \frac{2n+1}{3} \rfloor} \lfloor \frac{2n+1-3z}{2} \rfloor $ and because we are trying to find the "at least" we can use the fact that $x-1 \leq \lfloor x \rfloor \leq x$ and $x \leq \lceil x \rceil \leq x+1$ and with simple arithmetic we arrive at :

$$ \sum _{z=1}^{\frac{1}{3} (n+1-3)} \frac{1}{2} (-4+n)+\sum _{z=1+\frac{n+1}{3}}^{\frac{1}{3} (2 n+1-3)} \frac{1}{2} (2 n+1-3 z-2) = \frac{1}{12}(28-19n+3n^2) \approx \frac{n^2}{4}.$$

And thus concluding the proof by setting $c=\frac{1}{4}$(actually it have to be a little bit less than $1/4$).

(Note) your first side note is correct we can take for any value $c>0$ , $c n$ and apply the proof above to come up with approximation, also i think the second side note (the Generalization) is also true but proving it might be hard.

| cite | improve this answer | |
$\endgroup$

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.