Return to Answer

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$\tag{$*$}\label{483297_star}X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N$, $q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$\tag{$**$}\label{483297_starstar}X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$.

• Case 1: Suppose $q=1$ or $q=2$. Then \eqref{483297_starstar} holds with $C=\sqrt{2}$ using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
• Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By \eqref{483297_star}, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so \eqref{483297_starstar} holds with $C=2$.
• Case 3: Suppose $N \le q$. By \eqref{483297_star}, $X^2 \le 2q+8q\log q \le 10q \log q$, which implies that \eqref{483297_starstar} holds with $C=\sqrt{10}$. (In this case we can make $C$ as small as we wish by taking $q$ sufficiently large.)
• Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

Finally, we mention that \eqref{483297_starstar} is lossy compared to \eqref{483297_star} in the regime $N\ll q \log q$. A slightly better estimate is $$X \le C\left(\frac{N}{\sqrt{q}}+\sqrt{\max\{N,q\} \log q}\right).$$

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$\tag{$*$}\label{483297_star}X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N$, $q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$\tag{$**$}\label{483297_starstar}X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$.

• Case 1: Suppose $q=1$ or $q=2$. Then \eqref{483297_starstar} holds with $C=\sqrt{2}$ using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
• Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By \eqref{483297_star}, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so \eqref{483297_starstar} holds with $C=2$.
• Case 3: Suppose $N \le q$. By \eqref{483297_star}, $X^2 \le 3q+8q\log q \le 11q \log q$, which implies that \eqref{483297_starstar} holds with $C=\sqrt{11 }$. (In this case we can make $C$ as small as we wish by taking $q$ sufficiently large.)
• Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

Finally, we mention that \eqref{483297_starstar} is lossy compared to \eqref{483297_star} in the regime $N\ll q \log q$. A slightly better estimate is $$X \le C\left(\frac{N}{\sqrt{q}}+\sqrt{\max\{N,q\} \log q}\right).$$

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$(*)\, X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N,q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$(**)\, X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$.

• Case 1: Suppose $q=1$ or $q=2$. Then $(**)$ holds with $C=\sqrt{2}$ using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
• Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By $(*)$, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so $(**)$ holds with $C=2$.
• Case 3: Suppose $N \le q$. By $(*)$, $X^2 \le 2q+8q\log q \le 10q \log q$, which implies that $(**)$ holds with $C=\sqrt{10}$. (In this case we can make $C$ as small as we wish by taking $q$ sufficiently large.)
• Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

Finally, we mention that $(**)$ is lossy compared to $(*)$ in the regime $N\ll q \log q$. A slightly better estimate is $$X \le C\left(\frac{N}{\sqrt{q}}+\sqrt{\max\{N,q\} \log q}\right).$$

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$\tag{$*$}\label{483297_star}X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N$, $q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$\tag{$**$}\label{483297_starstar}X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$.

• Case 1: Suppose $q=1$ or $q=2$. Then \eqref{483297_starstar} holds with $C=\sqrt{2}$ using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
• Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By \eqref{483297_star}, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so \eqref{483297_starstar} holds with $C=2$.
• Case 3: Suppose $N \le q$. By \eqref{483297_star}, $X^2 \le 2q+8q\log q \le 10q \log q$, which implies that \eqref{483297_starstar} holds with $C=\sqrt{10}$. (In this case we can make $C$ as small as we wish by taking $q$ sufficiently large.)
• Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

Finally, we mention that \eqref{483297_starstar} is lossy compared to \eqref{483297_star} in the regime $N\ll q \log q$. A slightly better estimate is $$X \le C\left(\frac{N}{\sqrt{q}}+\sqrt{\max\{N,q\} \log q}\right).$$

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$(*)\, X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N,q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$(**)\, X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$. This is not qualitatively best possible, though: if $N \asymp q$ then $(**)$ gives $X\ll \sqrt{q}\log q$ while we have $X\ll \sqrt{q \log q}$ by $(*)$.

1. Case 1: Suppose $q=1$ or $q=2$. Then $(**)$ holds (with $C=\sqrt{2}$) using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
2. Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By $(*)$, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so $(**)$ holds with $C=2$.
3. Case 3: Suppose $N \le q$. By $(*)$, $X^2 \le 2q+8q\log q \le 10q \log q$, which implies that $(**)$ holds with $C=\sqrt{10}$.
4. Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

The authors seem to claim that if a real quantity $X$ satisfies $X \le N$ and $$(*)\, X^2\le N+\frac{2N^2}{q}+4(N+q)\log q$$ then $$X\le 2\frac{N}{\sqrt{q}}+\sqrt{q}\log q.$$ Here $N,q$ are positive integers. Your code clearly found a violation of this. Let me instead show that $$(**)\, X \le C\left( \frac{N}{\sqrt{q}}+\sqrt{q}\log q\right)$$ holds with $C=8$.

• Case 1: Suppose $q=1$ or $q=2$. Then $(**)$ holds with $C=\sqrt{2}$ using $X \le N$. From now on we won't use $X\le N$, and assume $q\ge 3$.
• Case 2: Suppose $N\ge 8 q\log q$. In particular $N \ge q$. By $(*)$, $X^2 \le N+\frac{2N^2}{q}+8N\log q \le \frac{4N^2}{q}$ and so $(**)$ holds with $C=2$.
• Case 3: Suppose $N \le q$. By $(*)$, $X^2 \le 2q+8q\log q \le 10q \log q$, which implies that $(**)$ holds with $C=\sqrt{10}$. (In this case we can make $C$ as small as we wish by taking $q$ sufficiently large.)
• Case 4: Suppose $q \le N \le 8q\log q$. Then $X^2 \le \frac{3N^2}{q} + 8N \log q \le \frac{3N^2}{q} + 64q\log^2 q$. Using the fact that $t\mapsto\sqrt{t}$ is subadditive, it follows that $$X \le \sqrt{\frac{3N^2}{q}} + \sqrt{64q\log^2 q} \le 2 \frac{N}{\sqrt{q}} + 8\sqrt{q}\log q.$$

Finally, we mention that $(**)$ is lossy compared to $(*)$ in the regime $N\ll q \log q$. A slightly better estimate is $$X \le C\left(\frac{N}{\sqrt{q}}+\sqrt{\max\{N,q\} \log q}\right).$$