Re: (finite)galois field

Mariano Suárez-Alvarez <mariano.suarezalvarez@xxxxxxxxx> wrote:
On Mar 26, 2:00 pm, Pubkeybreaker <pubkeybreaker@xxxxxxx> wrote:
Arturo Magidin wrote:
Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
magidin@xxxxxxxxxxxxxxxxx (Arturo Magidin) wrote:
Han de Bruijn <Han.deBruijn@xxxxxxxxxxxxxx> wrote:
Arturo Magidin wrote:
What else do you want to know?
What Finite Fields are good for .. , perhaps?
You mean, besides all of modern cryptology, linear programming,
and all that kind of thing?
I wasn't aware of applications of finite fields to linear programming.
Reference? or example?

I'm afraid I don't have anything specific; this may just be "coffee
hour gossip", but I was told this some time ago by someone who does
linear programming and operations research. She claimed that when
programming into a computer it was much better, for very large data
sets, to work over finite fields (specifically fields of order 2^n

Well, yes. The arithmetic is faster when the data has very large
precision requirements> simply because of the cost of multi-precision
arithmetic. But it will> not be faster because the number of variables
or constaints is large. Also, how do you lift> the results from a
local field with discrete topology to R??? Linear programming in done
over R. How does one maximize a function over a finite field when the
elements of the field have no ordering?????

While I do not know how one might solve problems of linear
programming using finite fields, experience has taught me to expect
people to come up with very creative ways of putting finite fields
to work. You seem to be thinking that the connection would be quite
direct, while it may surely be very subtle.

Take one example where you can use finite fields to solve a
seemmingly `continuous' problem:

Consider a finite set A of lines in the real plane, each one of which
is given by equations with integer coefficients. The problem is to
count the number R(A) of connected regions in which the plane is cut
by the lines of A. Well, it turns out that one can do this by
`reducing' the problem to the following one:

Consider a finite field F of prime order p, and consider the set A'
of lines that you get from the equations defining the lines of A when
you consider them to be happening in the plane F^2 over F---notice
this makes sense because the coefficients of the equations are integers,
which can be reduced modulo p. Now count the number of points of F^2
which are not on any of the lines of A', and call it N(p).

It turns out that there exists a polynomial f with integer
coefficients such that for all prime numbers p we have

N(p) = f(p) for all sufficiently large primes p.

and the funny thing is, one can reasonably easy show that the number
of regions in which the real plane R^2 is cut by the lines of A is
precisely f(-1)

Consider also local-global principles, e.g. Hasse's [1]. Also the
Grobner basis algorithm may be viewed as a generalization of the
simplex algorithm for linear programming, see [2],[3], and one
may profitably employ local techniques to compute Grobner bases.

--Bill Dubuque

[1] http://google.com/groups?threadm=6jhmdt$c05$1%40gannett.math.niu.edu

[2] Bernd Sturmfels, Algebraic Recipes for Integer Programming
http://front.math.ucdavis.edu/math.OC/0310194

[3] Bernd Sturmfels, Two MSRI lectures on Grobner bases (free download)
http://www.msri.org/communications/vmath/special_productions/production1/index_html
.

Relevant Pages

  • Re: (finite)galois field
    ... linear programming and operations research. ... finite fields, experience has taught me ... real plane, each one of which is given by ... equations with integer coefficients. ...
    (sci.math)
  • Re: (finite)galois field
    ... linear programming and operations research. ... finite fields, experience has taught me ... real plane, each one of which is given by ... equations with integer coefficients. ...
    (sci.math)
  • Re: (finite)galois field
    ... linear programming and operations research. ... finite fields, experience has taught me ... real plane, each one of which is given by ... equations with integer coefficients. ...
    (sci.math)
  • Re: (finite)galois field
    ... magidin@xxxxxxxxxxxxxxxxx (Arturo Magidin) wrote: ... I wasn't aware of applications of finite fields to linear programming. ...
    (sci.math)
Quantcast