5
$\begingroup$

Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?

Thank you.

Edit 1: This might be a slightly better question: Given a bound $R>r$, is there an algorithm to determine all values of $n$ such that $r^2$ is an integer? [Thank you Steven for the observation.]

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Without a bound on $r$, the answer is no; square roots are dense mod 1, so however close an approximation to $f$ you have, there are infinitely many square roots of whole numbers whose fractional part is that close to $f$. $\endgroup$
    – Steven Stadnicki
    Commented Jan 12 at 22:12
  • $\begingroup$ @StevenStadnicki, thank you! I will add an edit to the question. $\endgroup$
    – ReverseFlowControl
    Commented Jan 12 at 22:27
  • 1
    $\begingroup$ It's not too hard to show that you can only have one value of $n$ that makes $r^2$ an (exact) integer, incidentally; if $r=n+f$ with $r^2=q$, say, then $\left((m+n)+f\right)^2$ $= \left(m+(n+f)\right)^2$ $= m^2+(n+f)^2+2m(n+f)$ $=m^2+q+2m(n+f)$ and clearly the last term is irrational, since $f$ is and $m, n, q$ are all integers. But I'm not even sure if good lower bounds are known for $\min_{m,n\leq N}\left(\left|\sqrt{n}-\sqrt{m}\right|\bmod 1\right)$ as a function of $N$. $\endgroup$
    – Steven Stadnicki
    Commented Jan 12 at 22:50

3 Answers 3

Reset to default
5
$\begingroup$

Using the structure in the continued fraction expansion of a square root provides a relatively straightforward approach: expand out the continued fraction of $f$ until you see an initial segment that repeats with an even final coefficient $a_j$ and with the rest of the segment symmetric; then your candidate $n$ is $a_j/2$. If this gives an incorrect result, then continue expanding out $f$ until you see another repeating segment.

The complexity analysis is going to be dependent on the precision of $f$; assuming we have an approximation $f=\frac ab$, then the most reasonable parameter for analysis is $B=\log(b)$. Computing the continued fraction takes $O(B^2)$ bit operations using the Euclidean algorithm, and by using a suitable hash on the coefficients you should be able to find candidate repeating segments 'online' (that is, as the continued fraction digits of f become available) in effectively constant time per iteration. Since the (naive) multiplication to test a candidate also takes $O(B^2)$ time, this has total time roughly $O(B^2)$ (possibly with some smallish logarithmic factor to take into account the number of candidates to test). For comparison, the 'naive' approach of just testing every $n$ takes $O(r\cdot B^2)$ time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can't the length of this segment be $O(\sqrt r)$, though? $\endgroup$
    – Daniel Weber
    Commented Jan 13 at 21:18
  • $\begingroup$ @CommandMaster It can, but that's actually baked into the $O(B^2)$ estimate — you're doing operations on numbers of shrinking length. Note that this also means that the necessary $B$ can be $O(r)$ or so, too — in other words, you need an approximation to $f$ of closeness roughly $\exp(-r)$ to be able to find $r$ with any confidence. $\endgroup$
    – Steven Stadnicki
    Commented Jan 13 at 22:00
2
$\begingroup$

We have a number $f$, and we are looking for an integer $n$ such that $f^2 + 2f n = m$, where $m$ is an integer. This can be represented as two integer linear programs - program 1: $$\max{2nf - m} \\ f^2+2f n \leq m \\ 0\leq n \leq R$$ and program 2: $$\min{2nf - m} \\ f^2+2f n \geq m \\ 0\leq n \leq R$$

Integer linear programming with two variables can be solved efficiently, so this gives an efficient algorithm.

To know how many of digits of $f$ are necessary we will look at its convergents, until the denominator of one is more than $5 R$. Let's call that number $x$. Then we have $x = f + \varepsilon$ for $|\varepsilon| \leq \frac{1}{25 R^2}$, so for the real $n$ we have $2n x + x^2 = 2nf + 2n\varepsilon + f^2 + 2f\varepsilon + \varepsilon^2 = 2nf + f^2 + \varepsilon_2$ for $|\varepsilon_2| \leq \frac{2R+2}{25 R^2}$, but for other values of $m$ we have $2x m + x^2 = 2x n + x^2 + 2x (m-n)$ whose distance from an integer is at least $|\frac{1}{5R} - \varepsilon_2|$, and for $R > 4$, $\varepsilon_2$ is necessarily smaller.

As for the complexity, because the values in the continued fraction are bounded by $R$, we only need $O(\log R)$ digits. I'm not sure about the state of the art, but using a naive algorithm the complexity is $O(\log^2 R)$

Improve this answer
$\endgroup$
0
$\begingroup$

Just a trivial observation.
We know that $r=n+f$ is not an integer, while $n \in \mathbb{N} \wedge r^2 \in \mathbb{N}$.
Thus, $(n+f)^2 \in \mathbb{N} \Rightarrow (n^2+2 \cdot n\cdot f+f^2) \in \mathbb{N} \Rightarrow (2 \cdot n \cdot f + f^2) \in \mathbb{N}$ since $n^2$ is a nonnegative integer.
It follows that $(f\cdot(2 \cdot n + f)) \in \mathbb{N}$, where $(2 \cdot n) \in \mathbb{N}$ as well.

Of course, you can approximate $r$ better and better as you increase the number of significant digits of $f$ taken into account, but (unfortunately) we cannot find a closed formula to find the value you are looking for.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I did get this far. What I am looking for is an algorithm, not a formula, to approximate better and better answers. $\endgroup$
    – ReverseFlowControl
    Commented Jan 12 at 22:38
  • 1
    $\begingroup$ Oh, I see... then, I guess that we could get some of such algorithms, the hard part would be to get an efficient one. $\endgroup$
    – Marco Ripà
    Commented Jan 12 at 22:41
  • 1
    $\begingroup$ Other than trying everythng, I am open to anything that is better than the trivial one. $\endgroup$
    – ReverseFlowControl
    Commented Jan 12 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .