# Integer solution

For every prime $p$, does there exists integers $x_1$, $x_2$ and $x_3$ ($0\leq x_1, x_2, x_3 \leq \lfloor cp^{1/3}\rfloor$ and $c$ is some large constant) such that $\frac{p-1}{2}-\lfloor 2cp^{1/3} \rfloor \leq f(x_1,x_2,x_3) \leq \frac{p-1}{2}$, where, $f(x_1,x_2,x_3)=x_1+x_2+x_3+2(x_1x_2+x_2x_3+x_3x_1)+4x_1x_2x_3$.

• Notice that $$f(x_1,x_2,x_3) = \frac{(2x_1+1)(2x_2+1)(2x_3+1)}{2} - \frac{1}{2}.$$ Sep 9, 2015 at 11:18
• I wonder why there are votes to close this question. Doesn't seem obvious to me. Sep 9, 2015 at 21:11

I doubt that the lower bound $\frac{p-1}{2} - 2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p-1}{2} - cp^{1/2}$.

First of all, the inequality $\frac{p-1}{2}-cp^{1/2} \leq f(x_1,x_2,x_3) \leq \frac{p-1}{2}$ is essentially equivalent to $$p- O(p^{1/2}) \leq (2x_1+1)(2x_2+1)(2x_3+1) \leq p.$$

Let us take $y=\left\lceil\frac{p^{1/3}-1}{2}\right\rceil$. Then $$p \leq (2y+1)^3 < (p^{1/3}+2)^3 < p + O(p^{2/3}).$$

Define $$z = \left( \frac{(2y+1)^3 - p}{4(2y+1)} \right)^{1/2} .$$ Clearly, we have $z=O(p^{1/6})$.

Now, let us take $x_1 = y$, $x_2 = y - \lceil z\rceil$, $x_3 = y + \lceil z\rceil$ so that $$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$ $$< (2y+1)^3 - 4z^2(2y+1) = p.$$ On the other hand, we have $$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$ $$> (2y+1)^3 - 4(z+1)^2(2y+1) = p - O(p^{1/2}).$$

• That's nice, but why do you say that $p^{1/3}$ is unlikely. It seems plausible to me: by the three dimensional multiplication table problem one expects that there are about $x/(\log x)^c$ (for a suitable constant $c$) integers of size $x$ that can be factored into three factors of roughly equal size. Given that, I would expect that any interval of length $x^{\epsilon}$ around $x$ should contain such numbers (although proving this is another matter). Sep 10, 2015 at 20:17
• @Lucia: each of terms in the product must be of order $p^{1/3}$, that is the product (up to a factor) has form $(p^{1/3}+a)(p^{1/3}+b)(p^{1/3}+c)$ and I do not see a way here to make an error smaller than $O(p^{1/2})$, at least in the venue of the above proof. Maybe abundance of triples may help here, but that would be a different story. Sep 10, 2015 at 20:28
• I don't think so: for example the three variables can all lie between $p^{1/3}/10$ and $10p^{1/3}$. I think what I said is correct. (The three dimensional multiplication table problem counts $n$ of size $x$ being factored as $n_1n_2n_3$ with $n_1$, $n_2$, $n_3$ all of size $x^{1/3}$.) Sep 10, 2015 at 20:31
• Max, we search for an integer point in a region of a large volume, it would be strange if there is no. Sep 10, 2015 at 20:51
• @FedorPetrov: I'm not sure if it is large enough as compared to the interval length for the product. Say, if it holds for $p-O(p^{1/3})$, would it hold for $p-O(p^{1/4})$? Where is the exponent threshold here? Sep 10, 2015 at 22:16