# Disparity between polynomials and integers

Many results in number theory and algebraic geometry have an equivalent (or almost equivalent) result in integers and polynomial rings. It is also common to use techniques from one area to the other and prove results that resisted solution for a long time. In fact, we have very well known mathematical analogies between integers and ring of polynomials.

However, there are still problems that are easy on ring of polynomials and yet seem to be hard on integers. For example, factoring a polynomial is easy while factoring over the integer is one of the hardness assumption. Similarly, the polynomial variant of finding shortest vector for lattices is easy while it is hard over a lattice over integers. Again the polynomial variant of prime number theorem if proven in the case of integer will actually give a proof of Riemann Hypothesis. This list goes on and on.

I often wonder what is the intuitive reason for this disparity? Is it the case that the polynomial variant of a problem is always easy than that over the integers, or is there no such hardness reduction?

-

## migrated from crypto.stackexchange.comDec 14 '11 at 14:45

This question came from our site for software developers, mathematicians and others interested in cryptography.

I suppose this will depend a bit on which polynomial ring is used. – Paŭlo Ebermann Dec 13 '11 at 20:29
Can you please elaborate? – Jalaj Dec 13 '11 at 20:58
I've had a chat with the maths mods and others and we've come to the conclusion this would probably get a better audience on math.se although it has crypto aspects, so I'm moving it over there. If you don't have an account there, be sure to register and pick up your reputation/responses. – user892 Dec 14 '11 at 14:45
You've seen this? – J. M. Dec 14 '11 at 14:49
Something that someone should say is that number fields and function fields are exactly the fields whose completions are locally compact ("global fields"), so it is not strange that they would be closely related. (The purpose of the first half of Weil's Basic Number Theory is to develop "basic" number theory for global fields entirely from the point-of-view of local compactness.) Then, a person could say that function fields are simpler because the topologies are simpler. This is somewhat true, but the real reason is that we can use algebraic geometry, as Cam points out. – B R Dec 15 '11 at 6:11

As Paŭlo alludes to, it's hard to answer this carefully without knowing exactly what part of the analogy you're referring to. So this will be a pretty rough response.

First, there's a very surface-level (but still important) analogy between, say, $\mathbb{Z}$ and $\mathbb{C}[x]$, most of which stems from the fact that these two rings both have division algorithms. You get a Euclidean algorithm, gcd's, principal ideal theorem, etc., all of which lead to nice analogies: Lagrange interpolation vs. standard Chinese remainder theorem, Taylor series vs. $p$-adic expansions, etc. In this setting, probably the biggest reason that jumps to mind for the disparity you mention is the local phenomena. First of all, it's easier to add series in $\mathbb{C}[[x]]$ than it is in $\mathbb{Z}_p$: Taylor series add coefficient-by-coefficient, adding $p$-adic expansion involves "carries." Really what this is pointing to is the degree function being a significant boon in the polynomial case, being somewhat more rigid than $p$-adic valuation. Second, the fraction field $\mathbb{Q}$ of $\mathbb{Z}$ has a very weird completion that satisfies, of all things, the Archimedean property. For contrast, all the completions of $\mathbb{C}(x)$ are non-Archimedean and all of their residue fields are identical. You could even re-phrase this topologically -- $\mathbb{Q}$ has a connected completion, $\mathbb{C}(x)$ does not.

There is a stronger analogy between number fields and function fields over finite fields. Here your residue fields are finite fields like they are in $\mathbb{Z}$, hence the tightening of the analogy. This an area which lies under much of algebraic geometry, and is too bewilderingly vast to say much about here. Let me point you to a couple of MO questions that address this point:

Suffice it to say that the full force of algebraic geometry can come to bear on the function field side of things, so we get Weil conjectures, ABC, Riemann hypothesis for function fields, etc. It's probably worth mentioning that there are still plenty of instances where we don't know either of the analogous results (e.g., Artin's primitive root conjecture vs. Lang-Trotter, etc.)

Finally, let me mention (very) briefly a third level to this analogy, which is to introduce the notion of a Drinfeld module, designed (in a sense) to tighten once again the analogy. Again this is too gigantic a subject to say anything meaningful about in a paragraph, but I mention it as a point where the disparity starts to disappear and/or reverse — there are open questions about Drinfeld modules whose arithmetic analogues are known. Perhaps the commenters can think of an example that doesn't require pages of notation to write down.

-
Do you have a recommendation for a text at the upper undergrad or lower grad level on this? It sounds like an area I would like to read on. Thanks. – Ross Millikan Dec 15 '11 at 5:54
Ross, Some books dealing with number and function fields (or just the number theory of function fields) are Koch's Number Theory: Algebraic Numbers and Functions, Ramakrishnan and Valenza's Fourier Analysis on Number Fields (does both, despite the name), Rosen's Number Theory in Function Fields, Lorenzini's An Invitation to Arithmetic Geometry, Cohn's Algebraic Numbers and Algebraic Functions are all reasonable (some more than others). Maybe other people have further recommendations. (None of them use much "real" algebraic geometry, but Rosen and Lorenzini both prove the Riemann Hypothesis.) – B R Dec 15 '11 at 6:25
@RossMillikan: If you have some elementary number theory background, I think I'd recommend Rosen's book in BR's comment. You start seeing striking similarities -- and differences! -- between $\mathbb{Z}$ and $\mathbb{F}_q[x]$ within a page or two of getting started. – Cam McLeman Dec 15 '11 at 14:11
No worries. I liked your answer, so I wanted to spit-polish it and all... :) – J. M. Dec 15 '11 at 14:15
Thanks, Cam! I am not a hardcore number theorist. I work in cryptography and have an interest in number theory. The analogy I had in mind are more or less covered in second paragraph of your answer. Then I learned a bit about algebraic geometry from a course on Pairing based cryptography. I could see analogy here and there. I was surprised to see a simple solution to SVP, which basically started Lattice based cryptography and assumed to be hard on integers. This question was a in quest to get a better understanding of what's going on. – Jalaj Dec 15 '11 at 16:28