Terence Tao's Answer to the Erdős Discrepancy Problem | Hacker News Reader

Terence Tao's Answer to the Erdős Discrepancy Problem

quantamagazine.org

61 pointsretupmoc0123 comments

Here's a link to the paper: http://lanl.arxiv.org/pdf/1509.05363.pdf

There was more discussion on a previous HN submission regarding this discovery, as well:

https://news.ycombinator.com/item?id=10282230

The original Nature article had some very good background, including a link to the blog comment that gave Tao the impetus to explore a connection that led to this discovery (and which Tao credited in the paper):

http://www.nature.com/news/maths-whizz-solves-a-master-s-rid...

A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/1509.05363) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!

I like Erdos but I have to wonder how much of what he did matters if you look at results in binary instead of Base 10. It seems a lot of number theory seems to gloss over this basic fact. In number theory, it seems Wolfram's four categories explain "impossible problems" pretty simply.

What are you talking about? What base you write results in has nothing to do with number theory.

This is not a result that has anything to do with base representation, nor are the vast majority of number theoretic results.

We're being trolled, I think.

The only thing I can think of where base (sort-of) matters is that we have a formula for the Nth hexadecimal digit of pi, but not for the Nth decimal digit of pi. But I think that's due to lack of interest in making such a function, rather than some inherent reason why this could not be done.

I'm not really trying to troll, though it sounds that way. See below, for an example from Erdos' biography.

What does that even mean.

Number theory deals with numbers, not the representations of them. The properties of numbers dealt with in number theory exist independently of the base chosen in which to represent the numbers; in fact, a result from number theory (the basis representation theorem) is the formalization of what a "base" actually is and how to represent a number in an arbitrary base.

Number theory is like the metaphysics of maths. It's metamaths.

No, metamath is.

https://en.wikipedia.org/wiki/Metamathematics

That's set or category theory.

Your reply is what I always understood about number theory, and is true for many cases. But reading a number of important findings in number theory, when you look at the problem in binary - as Wolfram shows - every problem looks the same.

The unsolvable problems are always noise, the solved problems have a pattern. Like a class 3/4 automata, any unsolved math problem is simply an elaborate way of reaching the same conclusion: randomness, where you can't predict any given value but must compute it.

can you provide an example of an interesting problem in number theory which is dramatically transformed by approaching it in binary representation?

Would you be willing to elaborate? I'd be curious to hear a specific example of a result due to Erdős that no longer matters in binary, and also a specific impossible problem that's explained by Wolfram (with some detail so I can follow along, of course).

Erdos did a lot of work with primes, which if you're searching for patterns looking in binary makes a lot more sense than base 10.

For an example of base-10 centrism that I'm talking about (not specifically Erdos, but from the biography "The Man Who Loved Only Numbers" on page 106 there is a discussion of Stan Ulam writing integers in a spiral and finding primes connected by diagonals. What possible meaning does this pattern have outside of base 10?

This is the part of number theory that confuses me: why should such pattern finding matter, outside of base 10?

The pattern in the Ulam spiral is independent of the base we choose. They're just labels at regular intervals along a particular path. The fact that 3 is located at that particular point in the spiral is because its the third natural number, not because we write it as "3" in base-10. It's the 3rd natural number whether we write it as "3" (base 10), "11" (base 2), "10" (base 3), "|||", "三", a pictogram consisting of a hand holding up three fingers, or anything else.

In short, it's the _spiral_ that dictates the pattern, not how we label the points on the spiral.

As for what the pattern "means", well, it's hard to say and it might just our mind trying to make order where there is none. On the other hand, there are number theoretical conjectures that would account for certain aspects of the pattern, showing that it's more than just a psychological phenomenon.

Are you sure you're not trolling? I guess a troll wouldn't answer.

Thank you for answering.

In the example given in the book, Ulam creates rows of 10, so the base is significant to how the diagonals are found.

Yes I understand the basis of number theory is to abstract away such things as the base. But the number of times I've read about number theorists and how they found their way to some pattern or truth that seems to depend on base 10 seems weird.

So it is with this Ulam example: why is this a valid way to investigate the problem? It only seems valid in base 10 to me.

Without sharing the specific example, I don't know what to say. The Wikipedia page on the Ulam spiral is consistent with every representation/exposition I've seen and doesn't depend on the base we choose for the labels.

I don't even know what "rows of 10" means in the context of the Ulam spiral.

Yes I think the example of Ulam spiral in the Erdos book is not very good. The Wiki page is clear.

I wish I could find the example of Erdos work where I felt the same way... but the pile of his work is too immense.

Still, though, my karma hasn't taken enough of a beating: viewing a result set in binary and comparing it to automata output still seems a shortcut to understanding. That's an idea that is unpopular for sure.

There are definitely properties of numbers that are more easily stated in one base vs. another, but I don't see how an automata would matter. Any automata that can process strings in one base can be converted into an automata that can process strings in any other base.

An example of such a property is that a real number in the interval [0,1] is a member of the Cantor set if and only if it has no 1's in its base 3 representation (not a typo, yes, base 3).

For an example of using the Wolfram automata-view to look at a problem, think of Fermat's Last Theorem. Can a specific cube (or any higher power, really) be expressed as the sum of two other cubes?

The automata view shows us the answer because when you look at the list of cubes (or any higher power) as binary the resulting image meets the Wolfram test for randomness. Looking at these numbers in any other base has no obvious meaning, but in binary you can instantly see whether some set at least looks like a random automata.

When I look at number theory or indeed any insoluble math problem it always seems to be some variation on people trying to write an equation that satisfies something from a random automata.

Essentially all unsolved problems boil down to an argument about whether you believe automata show randomness or not.

Reply on news.ycombinator.com