Saturday, December 21, 2013

Polynomial Puzzle

Think about a set of integer values [0..N-1].  The total number of functions that can take two values from this set and return a third value from the same set is NN(i.e. the number of distinct truth tables that can be built for those values).  This is the same as the number of polynomials of the following form (where kfij is also drawn from [0..N-1]):



So the question bugging me is this:  Can every function that takes a pair of values in [0..N-1] and returns a value in [0..N-1] be represented by one of these polynomials?

I think it can, but I'm having a hard time proving it to myself.

If so, this gives us another (perhaps more meaningful) way to represent functions as numbers.  Any function f(a, b) like the one above could be encoded as a number as:



In this system, addition would always be encoded as N+1, and multiplication would be encoded as NN+1.

For what it's worth.

No comments:

Post a Comment