9 ms·

> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to estab

by fdej 5y ago

> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this. You can write down a completely explicit bound here using the Mahler-Mignotte root separation bound. More generally, for any algebraic expression involving algebraic numbers, you can bound a priori the number of digits you need to check to determine its sign. When you involve transcendental numbers, things do get much harder though.

pfortuny 5y ago
Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).
- syki 5y ago
  Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.
  - pfortuny 5y ago
    It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem.html https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.
    - syki 5y ago
      They are using a different notion of “measure” than the standard notion of absolute value of the difference. Under the standard measure every number is within epsilon distance of a rational for any positive epsilon. Thank you for the clarification.
      - pfortuny 5y ago
        Yes, of course. Sorry. It is an asymptotic result, so the meaning of "distance" is very blurry in my statement. I was replying to the previous comment which seemed to imply that knowledge.
        syki 5y ago
        I’ve never seen this before so thanks for the links and clarification. I learned something new.
deleted 5y ago
[deleted]
abetusk 5y ago
So, to state explicitly, given a list of positive integers, a_i, and coefficients, d_i \in {-1,1}, test whether \sum_i d_i sqrt(a_i) <=? 0. Now, construct a polynomial, P(z) = \prod_i (z^2 - a_i), and this gives a (univariate) polynomial so that a Mahler-Mignotte like bound can be used. I guess there's different levels of bounds you can use (Mahler, Mahler-Mignotte, Davenporte-Mahler-Mignotte [0]) but they all involve the discriminant, the deg to the deg power (n^n) and maybe some other factors which put it neatly in a polynomial time bit representation. One bound puts it in the 2^{-2s^2} range, for bit size s [1]. Why does this not solve it? The problem as stated on cstheory.stackexchange explicitly says the square roots are square roots of integers [2]. What am I missing? [0] https://arxiv.org/pdf/2005.07843.pdf https://arxiv.org/pdf/2005.07843.pdf [1] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... (pg 165, Lecture VI, Section 7, Root separation (pdf pg. 197)) [2] https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010 https://cstheory.stackexchange.com/questions/79/problems-bet... EDIT: I forgot to include the sqrt in the sum equation
- JadeNB 5y ago
  A request: please always link to abstract pages of articles, not directly to PDFs. https://arxiv.org/abs/2005.07843 https://arxiv.org/abs/2005.07843
  - balnaphone 5y ago
    May I ask, for what reason, please?
    - JadeNB 5y ago
      Personally, I prefer not to get surprise PDFs; but that's just personal. A better reason is that linking to the abstract page lets you navigate easily around the arXiv from there, including to the PDF if you desire; but there is no 1-click way to get from the PDF back to the abstract. (Of course, it's an easy matter of address munging, but even easier is not to have to do the munging.) A perhaps less satisfying reason is the same reason that one doesn't deeplink directly to an XKCD image, but rather to the XKCD page for the relevant cartoon: a courteous acknowledgement of the source.
devit 5y ago
Does that actually work? It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_polynomial_roots#Root_separation https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)). So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless the degree of the minimal polynomial is actually subexponential.
- abetusk 5y ago
  Why do you need the bounds for every combination of the N square roots? Isn't it enough to get the minimum distance between the two nearest elements in that list? If so, why not consider the 2N degree polynomial where P(z) = \prod (z^2 - a_i) ? This polynomial is only 2N degree and gives you the bound you actually care about, the number of bits needed to sum two numbers in the list. Since you're summing 2N of them instead of just one, you might need on the order of lg(N) more bits in your representation (so 2N + lg(N) bits, say) but this is still well within "polynomial" bits.
  - devit 5y ago
    Not clear how a lower bound on the absolute value of the difference of any two of the square roots would help give a lower bound on the absolute value of the difference of the two sums of square roots.
    - abetusk 5y ago
      Sorry to be obtuse, but I don't understand your hesitation. If you have a lower bound on the absolute value of the smallest difference of any/all pairs of roots, the lower bound on the sum of N of them is at most adding lg(N) bits. EDIT: I'm wrong, you're right. You've hit it on the head. My apologies. Just because there's bounds on pairwise roots, doesn't mean they then can be bounded when they're all summed together. In other words, say you have d_0 = |a_0 - a_1| and d_1 = |a_2 - a_3|, you might get into a situation where |d_0 - d_1] requires some exponential number of bits to represent.
woopwoop 5y ago
I would imagine (but note that I'm totally ignorant here) that this bound depends pretty poorly on the degree of the polynomial defining the expression (and pretty reasonably on the coefficients). Then when you sum two algebraic numbers, the degree of the polynomial defining the sum gets way worse (in general as bad as the product of the degrees). I would imagine this is the issue.
inasio 5y ago
I remember doing side by side plots of conservative Hamiltonian trajectories doing a standard Euler method (maybe even RK45), vs a symplectic method (which will maintains energy conservation). The RK45 implementation had a very nice symmetric pattern, but which was completely different from the one in the (correct) symplectic implementation. This was a useful eye opener for me to not just blindly rely on Matlab's ODE45 or other default solvers...

by fdej 5y ago

pfortuny 5y ago

Exactly: algebraic numbers, despite not being periodic, are in general "reasonably far from each other", and especially from rationals. I guess the problem can be solved using what you say, certainly. It is only transcendentals that can be "too near" each other, and near rationals (this is Liouville's result, which was improved later on, in a specific case the one you say).

syki 5y ago
Rational numbers are algebraic so how are algebraic numbers reasonably far from each other? Algebraic numbers are dense in the real number line.
- pfortuny 5y ago
  It is a specific statement by Liouville: if you can approximate a number "very well" using rational numbers, then it must be transcendental. https://mathworld.wolfram.com/LiouvillesApproximationTheorem.html https://mathworld.wolfram.com/LiouvillesApproximationTheorem... My statement above may be a bit confusing, though.
  - syki 5y ago
    They are using a different notion of “measure” than the standard notion of absolute value of the difference. Under the standard measure every number is within epsilon distance of a rational for any positive epsilon. Thank you for the clarification.
    - pfortuny 5y ago
      Yes, of course. Sorry. It is an asymptotic result, so the meaning of "distance" is very blurry in my statement. I was replying to the previous comment which seemed to imply that knowledge.
      - syki 5y ago
        I’ve never seen this before so thanks for the links and clarification. I learned something new.

deleted 5y ago

[deleted]

abetusk 5y ago

So, to state explicitly, given a list of positive integers, a_i, and coefficients, d_i \in {-1,1}, test whether \sum_i d_i sqrt(a_i) <=? 0. Now, construct a polynomial, P(z) = \prod_i (z^2 - a_i), and this gives a (univariate) polynomial so that a Mahler-Mignotte like bound can be used. I guess there's different levels of bounds you can use (Mahler, Mahler-Mignotte, Davenporte-Mahler-Mignotte [0]) but they all involve the discriminant, the deg to the deg power (n^n) and maybe some other factors which put it neatly in a polynomial time bit representation. One bound puts it in the 2^{-2s^2} range, for bit size s [1]. Why does this not solve it? The problem as stated on cstheory.stackexchange explicitly says the square roots are square roots of integers [2]. What am I missing? [0] https://arxiv.org/pdf/2005.07843.pdf https://arxiv.org/pdf/2005.07843.pdf [1] http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental... (pg 165, Lecture VI, Section 7, Root separation (pdf pg. 197)) [2] https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010 https://cstheory.stackexchange.com/questions/79/problems-bet... EDIT: I forgot to include the sqrt in the sum equation

JadeNB 5y ago
A request: please always link to abstract pages of articles, not directly to PDFs. https://arxiv.org/abs/2005.07843 https://arxiv.org/abs/2005.07843
- balnaphone 5y ago
  May I ask, for what reason, please?
  - JadeNB 5y ago
    Personally, I prefer not to get surprise PDFs; but that's just personal. A better reason is that linking to the abstract page lets you navigate easily around the arXiv from there, including to the PDF if you desire; but there is no 1-click way to get from the PDF back to the abstract. (Of course, it's an easy matter of address munging, but even easier is not to have to do the munging.) A perhaps less satisfying reason is the same reason that one doesn't deeplink directly to an XKCD image, but rather to the XKCD page for the relevant cartoon: a courteous acknowledgement of the source.

devit 5y ago

Does that actually work? It seems that the degree of minimal polynomial having as root the sum of N square roots might be up to 2^N, and if you then apply the bound at https://en.wikipedia.org/wiki/Geometrical_properties_of_polynomial_roots#Root_separation https://en.wikipedia.org/wiki/Geometrical_properties_of_poly... (where n = 2^N) you get a bound on the order of at least 2^N digits (more precisely 2^N (N + D)). So it doesn't seem to lead to a proof of a subexponential number of equal digits, unless the degree of the minimal polynomial is actually subexponential.

abetusk 5y ago
Why do you need the bounds for every combination of the N square roots? Isn't it enough to get the minimum distance between the two nearest elements in that list? If so, why not consider the 2N degree polynomial where P(z) = \prod (z^2 - a_i) ? This polynomial is only 2N degree and gives you the bound you actually care about, the number of bits needed to sum two numbers in the list. Since you're summing 2N of them instead of just one, you might need on the order of lg(N) more bits in your representation (so 2N + lg(N) bits, say) but this is still well within "polynomial" bits.
- devit 5y ago
  Not clear how a lower bound on the absolute value of the difference of any two of the square roots would help give a lower bound on the absolute value of the difference of the two sums of square roots.
  - abetusk 5y ago
    Sorry to be obtuse, but I don't understand your hesitation. If you have a lower bound on the absolute value of the smallest difference of any/all pairs of roots, the lower bound on the sum of N of them is at most adding lg(N) bits. EDIT: I'm wrong, you're right. You've hit it on the head. My apologies. Just because there's bounds on pairwise roots, doesn't mean they then can be bounded when they're all summed together. In other words, say you have d_0 = |a_0 - a_1| and d_1 = |a_2 - a_3|, you might get into a situation where |d_0 - d_1] requires some exponential number of bits to represent.

woopwoop 5y ago

I would imagine (but note that I'm totally ignorant here) that this bound depends pretty poorly on the degree of the polynomial defining the expression (and pretty reasonably on the coefficients). Then when you sum two algebraic numbers, the degree of the polynomial defining the sum gets way worse (in general as bad as the product of the degrees). I would imagine this is the issue.

inasio 5y ago

I remember doing side by side plots of conservative Hamiltonian trajectories doing a standard Euler method (maybe even RK45), vs a symplectic method (which will maintains energy conservation). The RK45 implementation had a very nice symmetric pattern, but which was completely different from the one in the (correct) symplectic implementation. This was a useful eye opener for me to not just blindly rely on Matlab's ODE45 or other default solvers...