10
$\begingroup$

Let us say I have 10,000 digits started from some point (lets say the 16th digit) of the decimal expansion square root of some arbitrary number, like 13. Is there any way I can get back the original formula, which was sqrt(13) ? Can anyone provide some mathematical proofs that have been done regarding this subject?

$\endgroup$
4
  • 6
    $\begingroup$ Are we presuming that the irrational number has a closed form formula to begin with? Most irrational numbers do not have a closed form which can be written down at all! $\endgroup$
    – Cort Ammon
    Nov 27 '15 at 21:28
  • $\begingroup$ Yeah. (word count) $\endgroup$
    – michaeljan
    Nov 27 '15 at 21:51
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Integer_relation_algorithm $\endgroup$ Nov 27 '15 at 22:06
  • $\begingroup$ Although you can never be certain this can give you a pretty good guess. $\endgroup$
    – PyRulez
    Nov 27 '15 at 23:31
8
$\begingroup$

If the irrational number is algebraic of degree two (i.e. is a root of a quadratic polynomial with integer coefficients), then there is a fairly reliable way to make an informed guess about the original value. Your sample case falls into this category, being equal to $10^{16} \sqrt{13} - n$ for some integer $n$. It's important to note that the vast majority of irrational numbers don't fall into any special category, let alone this particular one.

You will want to look up continued fractions. If the irrational is of the very special type I described above, then the continued fraction will be eventually periodic (infinitely repeating), very analogous to a decimal expansion being periodic for rational numbers.

Now, granted, if you only have a finite number of digits you can only extract a finite number of terms in the continued fraction expansion, so you can never have enough precision to be absolutely sure of the number's identity. Nevertheless, if you have 10000 digits you can likely extract thousands of terms. If you see that the terms look like, say,

$$[3; 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 23, 8, 4, 3, 23, 8, 4, 3, 23, 8, 4, 3, 23, 8, 4, 3, 23, 8, 4, \ldots]$$

and that the patten of "8, 4, 3, 23" continues repeating thousands of times until you reach the precision allowed by your input sample, it would be reasonable to guess that it continues forever, and then there are simple ways to compute the exact value that it would be assuming that is the case.

$\endgroup$
1
  • 2
    $\begingroup$ Hmmm, I underestimated the impact of the $10^{16}$ term. It will generally cause the period of continued fraction to be too large to be detected with just 10000 digits. So any technique to solve this effectively would probably have to take into account the specialness of $10^{16}$ being a power of $10$. This makes Yves Daoust's answer more practical, I think. $\endgroup$
    – Erick Wong
    Nov 27 '15 at 20:51
7
$\begingroup$

No matter how many digits of an irrational number you know, there will be an infinite amount of irrational (and even rational!) numbers that start with those digits. So your 'formula' will only give you one of them.

Also, there are a lot more (in a very specific sense) irrational numbers than formulas (of finite length, as Brian Tung pointed out).

$\endgroup$
12
  • $\begingroup$ There are more irrational numbers than formulas of finite length. (I know, it's a subtle point, but since irrational numbers have infinite length almost by definition...) $\endgroup$
    – Brian Tung
    Nov 27 '15 at 20:28
  • $\begingroup$ That's what I was thinking. Like if I had some digits of an irrational number, could I guess the next digits? It's for my school project on cryptography. $\endgroup$
    – michaeljan
    Nov 27 '15 at 20:29
  • $\begingroup$ True, edited the post. And 4everPixelated, you will probably not guess the number, unless you have extra information about it. $\endgroup$
    – Mauro
    Nov 27 '15 at 20:32
  • 1
    $\begingroup$ You can't always guess the irrational number; if you could, then there would be no more information in the irrational number than there was in the truncation you observed. If I see, for instance, $2.7182818284$, I might guess that we'll see $59045$ next, but I can never know that for sure. I think we'd have to know more about your school project to answer more definitively. $\endgroup$
    – Brian Tung
    Nov 27 '15 at 20:33
  • 1
    $\begingroup$ An irrational number's decimal is a trivial example of a formula of infinite length. $\endgroup$
    – Brian Tung
    Nov 28 '15 at 16:36
4
$\begingroup$

If you know it's a square root and have a rough bound, you can indeed find it. Let's say $\sqrt{x} = 10^{-16} (y + z)$ where $y$ is a positive integer and $0 < z < 1$ (so the digits of $z$ are the digits of $\sqrt{x}$ from the $16$'th on). You know many of the digits of $z$, but not $x$ or $y$. Thus $z = 10^{16} \sqrt{x} - y$ satisfies the quadratic equation $$ z^2 = b - a z $$ where $$\eqalign{b &= 10^{32} x - y^2\cr a &= 2 y\cr}$$

In your example, suppose we know the 84 digits of $\sqrt{13}$ after the first $16$:

$$ z = 0.9311922126747049594625129657384524621271045305622716694829301044520461908201849 $$

We don't know $13$, but we suspect $x$ is not too big, so $a$ (and thus also $b$) should be something on the order of $10^{16}$.

Using Maple's PSLQ function with Digits = 64, we find an approximate integer relation between $1$, $z$ and $z^2$:

$$-67149225402228336 + 72111025509279784 z + z^2 \approx 0$$

from which we get

$$ \eqalign{ y &= 72111025509279784/2 = 36055512754639892\cr x &\approx (-67149225402228336 + y^2)/10^{32} = 13\cr}$$

$\endgroup$
3
$\begingroup$

If the search is limited to the square roots of integers, the answer is positive: it suffices to compute all square roots in turn and try and match the decimals. If the given digits were really taken from a square root, the search will find it. If they were taken "randomly", the search may probably find a number as well.

Needless to say, this is just a theoretical approach as this might take a huge amount of time/resources.

$\endgroup$
6
  • $\begingroup$ If you're limiting your search to square roots only wouldn't you multiply the given digits by themselves first in order to cut the search space down? $\endgroup$
    – postmortes
    Nov 27 '15 at 20:41
  • 1
    $\begingroup$ The interesting question though is: Are there only finitely many square roots of integers with a given sequence of numbers in position 16 through 10016? Almost certainly yes, but interesting $\endgroup$ Nov 27 '15 at 20:41
  • 1
    $\begingroup$ @postmortes: could you elaborate ? $\endgroup$
    – user65203
    Nov 27 '15 at 20:42
  • 3
    $\begingroup$ @TrevorRichards: by the pigeonhole principle, if you take the square roots of increasing integers, at least one 16+10000 sequence of digits will reappear, and it will do so as many times as you want. $\endgroup$
    – user65203
    Nov 27 '15 at 20:48
  • 1
    $\begingroup$ @YvesDaoust - sadly not, I've spent the last ten minutes convincing myself that you don't actually get any better information by trying that approach. Sorry! $\endgroup$
    – postmortes
    Nov 27 '15 at 20:53
2
$\begingroup$

ETA2: Sorry, I misread the question to mean that the number could be any irrational value, not the square root of an integer. Read on with that in mind...

I think there are only heuristics. This site

https://isc.carma.newcastle.edu.au/

(called the Inverse Symbolic Calculator) may be relevant to your interests.

ETA: I think what it does is recursively construct expressions from a large database of atomic values and sort them by best match. So there's not much theory behind it, I don't think—just best effort.

You may also be interested in Dirichlet's Approximation Theorem:

https://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem

and Hurwitz's Theorem:

https://en.wikipedia.org/wiki/Hurwitz%27s_theorem_%28number_theory%29

$\endgroup$
0
$\begingroup$

A slightly more complicated way of thinking about it, but an interesting one I think, is the following. Any compact (closed and bounded) subset of $\mathbb R$ is in bijection with every other one*. Suppose you know the first $N$ digits. Then the possible remaining numbers form a compact subset of $\mathbb R$, in particular (wlog your numbers are in $[0,1]$ for typesetting ease!) $$[0.(r_1)(r_2)...(r_N), \ \ 0.(r_1)(r_2)...(r_N+1)].$$ (Note that there are some fiddly technicalities if the last digit it $9$, and note that $0.9999... = 1$.) Thus you still have the same "quantity" of numbers left -- more precisely, you still have the same cardinality. Thus you have "no" more information, in the sense that if you were to guess, you'd still have probability $0$ of being correct.

$\endgroup$
0
$\begingroup$

It's well known (I assume) that in the p-adic coefficient of a natural number: $$d_{n,p,j}= \Bigl\lfloor{n\,{p}^{\,j- {\lfloor \ln_p(n)\rfloor} -1}} \Bigr\rfloor-p\Bigl\lfloor{n\,{p}^{\,j- {\lfloor \ln_p(n)\rfloor} -2}} \Bigr\rfloor$$ $$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\operatorname{(1)}$$ as seen in the p-adic expansion of that number: $$n=\sum_{j=1}^{\lfloor \ln_p(n)\rfloor+1}d_{n,p,j}\,p^{\,\lfloor \ln_p(n)\rfloor+1-j}\quad\forall n \in \mathbb N$$

can likewise be used to separate any positive real number into it's integer and fractional parts:

$$\lfloor x\rfloor=\sum_{j=1}^{\lfloor \ln_p(x)\rfloor+1}d_{x,p,j}\,p^{\,\lfloor \ln_p(x)\rfloor+1-j}\quad\forall x \in \mathbb R^{+}$$

$$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\operatorname{(2a)}$$ $${\{x}\}=\sum_{j=\lfloor \ln_p(x)\rfloor+2}^{\infty}d_{x,p,j}\,p^{\,\lfloor \ln_p(x)\rfloor+1-j}\quad\forall x \in \mathbb R^{+}$$

$$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\operatorname{(2b)}$$

What this should demonstrate to you is that decimal expansion is well ordered, and you can use this process above to compute any number of decimal places you like, however as has been stated in previous answers, you can find any number of numbers, rational, irrational, algebraic or transcendental, that are a linear combination of numbers including the one that has the decimal expansion you have computed a portion of in the manner above, but even if you hypothetically computed the number's decimal expansion to infinity, or it's p-adic expansion for any natural number $p \gt 1$ for that matter, this will never provide you with a conclusive result regarding the number's rationality.

$\endgroup$

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.