[abetusk]

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

[1] 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-bet...

EDIT: I forgot to include the sqrt in the sum equation

[abetusk]

I'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

[JadeNB]

A request: please always link to abstract pages of articles, not directly to PDFs.

https://arxiv.org/abs/2005.07843

[rhaps0dy]

You 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

[balnaphone]

May I ask, for what reason, please?

[JadeNB]

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.

[pvg]

These 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]

I 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]

The 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]

Multiple 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?

[FabHK]

I was going to add that some people on slow connections might not want to download large PDFs.

However, in today's web, the html page with the abstract (one paragraph) was a 2.5 MB download, while the 15 page paper including a figure was just 800 kB.

[xxpor]

That's honestly an incredible indictment of today's web, isn't it?

[doetoe]

In my particular case PDFs linked from hacker news (accessed through the nextcloud feed reader) end up in my phone's downloads, which in that way fills up with PDFs I only wanted to read once.

[kadoban]

There 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.

[muggermuch]

So 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.