About a month ago, I worked out how many functions had the following properties:
Since then, I've figured out how to write out pretty equations in Google Docs. (Can you tell?) The number of such functions, expressed prettily, is:
This type of function probably has a proper name, but I don't know what it is. For the purpose of this blog post, I'll call these "nifty functions". A month ago, I thought I had figured out how to generate the truth table for the nth nifty function, but it turns out I was wrong. Painfully wrong.
A couple weeks ago, I wrote some code that will take a truth table and solve for the simplest modular polynomial that would generate the truth table. I thought it would be neat to see what the nifty functions looked like as polynomials.
That's where I realized I was painfully wrong about how easy it would be to generate the truth table for the nth nifty function. While it appears I was right about the number of these functions, generating the truth table turned out to be far more complicated than I thought. However, I have emerged tired but victorious. I can now list out polynomials that represent the nifty functions for a given (mod P).
Naturally, quite a bit of processing is required relative to P, so I am only exploring small primes at the moment. I'm interested in two questions:
1. If you have a polynomial expression that is nifty in (mod Pa), is it also nifty in (mod Pb)?
2. Are there nifty functions where f() can be processed in polynomial time, but its inverse g() cannot be?
Given the tools I have developed so far, I should be able to test these questions experimentally for small P. In the mean time, I leave you with one of the most complex nifty polynomials for (mod 5).