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

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

1 Answer 1


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

  • 1
    $\begingroup$ 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). $\endgroup$
    – Lucia
    Sep 10, 2015 at 20:17
  • $\begingroup$ @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. $\endgroup$ Sep 10, 2015 at 20:28
  • $\begingroup$ 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}$.) $\endgroup$
    – Lucia
    Sep 10, 2015 at 20:31
  • $\begingroup$ Max, we search for an integer point in a region of a large volume, it would be strange if there is no. $\endgroup$ Sep 10, 2015 at 20:51
  • $\begingroup$ @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? $\endgroup$ Sep 10, 2015 at 22:16

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.