9
$\begingroup$

A field is an ordered triple $(F, +,\cdot)$ of a set $F$ and binary operations $+,\times$ on $F$ such that $(F,+)$ and $(F\backslash 0,\times)$ are abelian groups satisfying the distributive laws $\forall a,b,c \in F:\begin{cases} a\times(b+c)=(a\times b)+(a\times c)\newline (a+b)\times c= (a\times c)+(b\times c) \end{cases}$.

Someone mentioned that the "interplay" between the additive structure $(F,+)$ and the multiplicative structure $(F\backslash 0,\times)$ in a field is still "not well understood". Another friend mentioned that the distributive laws fully characterize the relationship between $+,\times$ by definition, but that these laws are "not fully understood".

What is this deep understanding? What is known and what is unknown? Restrict this question to specific fields if necessary, like finite.

EDIT: I should clarify that this came up during a discussion of Wang's attacks on hash functions in cryptography.

$\endgroup$
1
  • 6
    $\begingroup$ My personal feeling is that the polynomial description of fields is very unintuitive: I have learned and forgotten many details more than once over the years. To my mind, a much more intuitive (but not computationally better) approach is to treat elements of $\mathbb{F}_{p^r}$ as matrices over $\mathbb{F}_p$: the additive and multiplicative structures coexist nicely then. This approach reduces much of the theory of finite fields concerned with the interplay of which you speak to representation theory. It is detailed in a cute article by Wardlaw: jstor.org/discover/10.2307/2690850 $\endgroup$ Mar 16, 2013 at 23:05

4 Answers 4

12
$\begingroup$

The theory of fields is an undecidable theory, and so one cannot give a computable procedure for deciding whether a given statement in the formal language of fields is true or not in all fields. This is a sense in which this theory is not fully understood. Indeed, the situation is that we have proved that we can have no computably complete understanding of the theory of fields.

The theory of fields is not what is called essentially undecidable, however, since the theory of fields has a complete decidable extension, namely, the theory of real-closed fields, which is decidable. (There are also many other trivial extensions of the theory that are decidable, such as the theories of various specific finite fields.)

Furthermore, James Ax proved that the theory of finite fields is decidable. Thus, we have a computable procedure to decide whether a given statement is true or not in all finite fields, which is surely shows a very good measure of understanding in that context. (Thanks for correction of my earlier remark by Donu Arapura.)

$\endgroup$
5
  • 2
    $\begingroup$ If a logician said that the interplay of $+$ and $\times$ was not well understood, I would expect them to mean something like this. If an algebraist (or algebraic geometer, number theorist, etc) said it, though, I would expect them to mean something very different. Was the OP referring to comments from a logician, or an algebraist, I wonder? $\endgroup$ Mar 16, 2013 at 23:49
  • $\begingroup$ Peter, probably you are right. My only point is that the undecidability of the theory should be at least part of the conversation. $\endgroup$ Mar 17, 2013 at 0:11
  • 1
    $\begingroup$ One could add to Joel's answer the observation that the first-order theory of abelian groups -- whose statements are interpretable in structures like $(F, +)$ and $(F^\ast, \cdot)$ taken on their own -- is meanwhile decidable. So the interplay given by the distributivity axiom is critical in some sense. $\endgroup$
    – Todd Trimble
    Mar 17, 2013 at 1:53
  • $\begingroup$ Peter: perhaps none of the above, maybe a computer scientist? Joel: I'm sorry to nitpick, and I'm certainly no expert, but didn't Ax prove decidability of the theory of finite fields? $\endgroup$ Mar 17, 2013 at 2:29
  • $\begingroup$ Oops, Donu, you are right, and I have edited. $\endgroup$ Mar 17, 2013 at 11:13
11
$\begingroup$

This answer is just adding flesh to @Frank Thorne's earlier answer. He noted that the idea of "addition and multiplication interacting" comes up in additive combinatorics. Perhaps the most obvious instance of this is in the study of the sum-product phenomenon (SPP).

Roughly speaking the SPP asserts that any subset of a field $F$ must ``grow'' under either addition or multiplication. The way one makes this rough statement precise depends on the field in question. Let me consider two instances:

Suppose $F=\mathbb{R}$. In this situation the central conjecture is due to Erdos and Szemeredi:

For every $\varepsilon\in (0,1)$, there exists $c>0$, such that for $A$ a finite subset of $\mathbb{R}$, $\max(|A+A|, |A\cdot A|) \geq c |A|^{2-\varepsilon}$.

This conjecture is still open, however progress has been made. The strongest statement is (I believe) due to Solymosi, but it's also worth mentioning the work of Elekes. With a very simple argument, he connected SPP to questions in incidence geometry in the plane and to the idea of the crossing number in $\mathbb{R}^2$ to prove:

There exists $c>0$, such that for $A$ a finite subset of $\mathbb{R}$, $\max(|A+A|, |A\cdot A|) \geq c |A|^{5/4}$.

One last remark - another way of thinking about the Erdos-Szemeredi conjecture is this: it says that a set $A$ of real numbers cannot simultaneously be both a geometric progression and an arithmetic progression (since, by results of Freiman and others, these are the classes of sets that do not grow under multiplication and addition, respectively).

Suppose $F=\mathbb{Z}/p\mathbb{Z}$. In this situation, the central result is due to Bourgain, Katz and Tao:

For every $\delta>0$ there exists $\varepsilon>0$ and $c>0$, such that for $A$ a finite subset of $\mathbb{Z}/p\mathbb{Z}$ with $|A| < p^{1-\delta}$, we have $\max(|A+A|, |A\cdot A|) \geq c |A|^{1+\varepsilon}$.

The statement is slightly different to that in $\mathbb{R}$ because it is clear that sets that are almost as large as the field itself cannot possibly grow.

This result has been generalized in various ways to arbitrary finite fields. However in this more general setting one has to deal with the presence of finite subfields (again this does not crop up in $\mathbb{R}$), and so statements tend to be slightly technical. There is also a wealth of work giving values for $\varepsilon$ when $\delta$ is, say, $\frac12$, as well as a lot of work connecting this result to geometry over finite fields (in the spirit of the work of Elekes).

$\endgroup$
4
  • $\begingroup$ In the Bourgain-Katz-Tao theorem that you quote, $\delta$ is introduced but never mentioned again. $\endgroup$ Mar 22, 2013 at 13:54
  • $\begingroup$ oh, right, yes, i missed a clause! correcting it now... $\endgroup$
    – Nick Gill
    Mar 25, 2013 at 9:39
  • $\begingroup$ Strictly speaking, Jean, Nets, and myself only established the above bound in the regime $p^\delta < |A| < p^{1-\delta}$. The extension to the full range $|A| < p^{1-\delta}$ was done shortly afterwards by Bourgain, Glibichuk, and Konyagin. $\endgroup$
    – Terry Tao
    Mar 26, 2013 at 16:32
  • $\begingroup$ Good point - thanks for spreading the credit! $\endgroup$
    – Nick Gill
    Mar 26, 2013 at 17:31
6
$\begingroup$

Large parts of number theory deal in some way with the interplay between addition and multiplication in fields and subrings thereof. This concerns in particular all questions which are related in some way to prime numbers or prime factorization. I hope you agree that not everything here is "well understood" so far.

$\endgroup$
5
$\begingroup$

This question comes up in the subject of additive combinatorics. "Additive combinatorics" is a bit difficult to define precisely, and indeed Ben Green, one of the leading experts in the subject, has expressed this sentiment rather colorfully.

Questions along the lines of yours are considered in this field. Green's review is an excellent overview of what additive combinatorics is all about, see p. 23 of these notes of Soundararajan for a theorem related to your question, and Tao and Vu's book is the authoritative reference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.