# Analytic Number Theory without Pigeonhole Principle [closed]

I don't know if this is an appropriate question for this website, but I will try my luck.

I am an undergraduate student, and recently I became interested in analytic number theory. When I started reading introductory material in the subject, I got the idea that most "structures" and most ideas in proofs are heavily based on combinatorial-like ideas. For example, the Pigeonhole Principle is used extensively.

Of course some people would find this very obvious since the subject is concerned primarily with things like "counting the number of primes less than a given magnitude". However, I would still argue that things could have been very different and combinatorial techniques could have been ineffective.

So my question is: First of all, in general, could techniques from combinatorics be replaced by other methods in order to achieve the same results we have today.

Secondly, is there a "bigger picture"? In other words, do we know of a higher mathematical structure which explains this intersection between analytic number theory and combinatorics.

Please excuse me if you find that questions are badly formulated. After all, English is not my mother language.

## closed as too broad by Nate Eldredge, Andy Putman, Stefan Kohl, Yemon Choi, Chris GodsilJul 23 '15 at 0:44

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• I love the axiom of choice, but I have to object to ". . . without which pretty much nothing works in math": plenty of things don't involve choice at all, and many things work better without it and with determinacy (or similar) instead. – Noah Schweber Jul 22 '15 at 21:53
• I think your impression that analytic number theory is heavily based around combinatorial ideas is incorrect. While I am far from an expert in the subject, my impression is that most work in the subject uses serious analytic tools that are not really combinatorial, e.g. Fourier analysis as in the circle method and complex analysis. – Andy Putman Jul 22 '15 at 22:00
• @AlexDegtyarev: Isn't "do this without that" the whole idea of reverse mathematics? I think this particular question is too broad for this site, but in general it's a legitimate sort of question to ask. – Nate Eldredge Jul 22 '15 at 22:04
• Maybe these go some way towards an answer: mathoverflow.net/questions/36405/… mathoverflow.net/questions/61632/… – Dan Piponi Jul 22 '15 at 22:12
• The question that is specifically asked here is quite unclear to me, but nevertheless I believe that reading Elkies's "What is analytic number theory?" might help to clear up the underlying question. – user9072 Jul 22 '15 at 23:06

To my perception, the reason "elementary" number theory (which includes some "analytic" number theory, which, ironically, can be manifest in ways which involves no analysis whatsoever) seems "combinatorial", is that a naive sense of "combinatorial" is a fairly superficial one of "involving no structure or big prerequisites".

So, sure, elementary number theory can be done, if one insists, without too many prerequisites. That doesn't really mean that it's "combinatorial", unless the latter is taken as synonym for "without prerequisites". I do suspect that this slippery slope is what leads many people to ask questions based on an over-interpretation of the facts... and mis-labeling.

The specific example of "pigeon-hole principle" is misleading in at least two ways. One, if this is "combinatorial", then everything is combinatorial. Second, there are certainly very-non-finitistic versions of this, very non-elementary, so it's hard to really claim that this is "combinatorial" in any sense that usefully distinguishes it for "other mathematics".

A second way that "a higher something" may "suggest" an interaction between elementary number theory and "combinatorics" is simply that many more sophisticated structures can be denatured to an extent, to "combinatorial/finitistic/formulaic" assertions, which can sometimes be a sufficient skeletal causality to prove some number-theoretic facts. But this is a special case of the general principle that anything can be denatured (selectively or accidentally or...) to look "combinatorial" but still manage to minimally succeed.

E.g., Fermat's little theorem can be construed as something "combinatorial" about binomial coefficients ... but it also can be viewed as an instantaneous consequence of Lagrange's theorem in group theory.

At a different extreme, if someone wants to claim that "sieving" (e.g., see recent work of Zhang, Maynard, Tao, et al) is "combinatorial", well, ... :)

So, quite seriously, I think that perception of number theory as "combinatorial" is misguided, perhaps misguided semantically, unless one makes the word "combinatorial" be so broad as to be useless.

• Well, I agree that in some sense all of mathematics is combinatorial. However it seems to me (of course I could be completely wrong) that some areas are more so than others (finite group theory vs differential geometry, for example). As for analytic number theory, it seems to me that there is an intersection between the discrete and the continuous, therefore, I think that there is a "higher structure" which explains this intersection. – user64472 Jul 22 '15 at 23:05
• It is still not clear to me what you mean by "analytic number theory". Please clarify? There is much potential ambiguity in that label. E.g., do you mean Iwasawa-Tate theory of zeta functions? Jacquet-Langlands? Sieves? The Zhang-Maynard-Tao business? Subtle things about moment estimates? Subconvexity? "The thing is", most of these are not really "combinatorial" or "discrete" in any operational sense, so there's some element of mis-reference, to my mind. Please clarify? – paul garrett Jul 22 '15 at 23:17
• By analytic number theory, I mean sieve theory especially as you said, all the Zhang-Maynard-Tao business. – user64472 Jul 22 '15 at 23:24
• When I describe a result as "combinatorial" I usually mean that it involves delicately counting something (as opposed to computing, comparing, axiomatizing...) I think the OP is asking: "Can you do number theory without counting?" It doesn't seem intuitively likely, but who knows? – Paul Siegel Jul 23 '15 at 0:10