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{p1}{2}\lfloor 2cp^{1/3} \rfloor \leq f(x_1,x_2,x_3) \leq \frac{p1}{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$– Max AlekseyevSep 9, 2015 at 11:18

4$\begingroup$ I wonder why there are votes to close this question. Doesn't seem obvious to me. $\endgroup$– LuciaSep 9, 2015 at 21:11
1 Answer
I doubt that the lower bound $\frac{p1}{2}  2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p1}{2}  cp^{1/2}$.
First of all, the inequality $\frac{p1}{2}cp^{1/2} \leq f(x_1,x_2,x_3) \leq \frac{p1}{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$– LuciaSep 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$– LuciaSep 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 $pO(p^{1/3})$, would it hold for $pO(p^{1/4})$? Where is the exponent threshold here? $\endgroup$ Sep 10, 2015 at 22:16