4 ms·
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 po
by 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 agoA 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 agoMay I ask, for what reason, please?
- JadeNB 5y agoPersonally, 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.
- pvg 5y agoThese are fine but pretty idiosyncratic. HN doesn't have citation rules so the 'always' seems overstated. People linking papers are already going the extra mile for the benefit of others and we don't really need to berate them about how they're holding their generosity wrong.
- JadeNB 5y agoI didn't mean to come across as berating, but rather as suggesting a better way to link. I hoped that 'request' and 'please' would set the proper tone, but am certainly open to better ways of wording it. I meant 'always' to indicate that I specifically wasn't just complaining pointlessly about the present case, but rather talking about future links; but I can see how it came across like the scolding 'always' as in a phrase "you always do this."
- balnaphone 5y agoThe PDF contains the abstract right at the top, along with full attribution, and often uses less bandwidth. In most browsers, selecting the title and first author then right-clicking "search" allows a user to find related material on the open web. My personal preference is the PDF link. Your request was perfectly polite, I was simply wondering what your rationale was for it.
- xxpor 5y agoMultiple people have said they prefer not getting surprise PDFs. Could you elaborate on why? It's never something I've ever thought about. PDFs open in the browser now for most people, so it seems like it shouldn't make much difference?
- kadoban 5y agoThere may be more of a security risk with PDFs, hard to say though. This was likely more of an issue back when using an external program to view them was a requirement.
- 5y ago
- muggermuch 5y agoSo people can determine for themselves whether they want to download the PDF, by reading the abstract first. This has always been a point of petty annoyance for me as well.
- rhaps0dy 5y agoYou can also go straight to the abstract from PDF links using the "Redirectify" browser add-on for Firefox and Chrome. https://github.com/imurray/redirectify https://github.com/imurray/redirectify
- abetusk 5y agoI'm wrong. The Mahler-Mignotte only works for pairs of roots and doesn't say anything about the absolute value of the sum, at least in the way I was thinking about it. There may be a way to "fix it up" but not that I see and I suspect folks who've studied this in earnest are aware of Mahler-Mignotte and understand why it can't be used to solve this problem. Thanks to @devit [0] who has understood why the Mahler-Mignotte tactic doesn't work. Just because you can bound the bit complexity of pairs of roots doesn't mean you can bound the complexity of all the 2^N possible {-1,1} combinations of them. At least, I don't see how it can be done simply. [0] https://news.ycombinator.com/item?id=30059545 https://news.ycombinator.com/item?id=30059545