Re: R.J. Lipton and K.W. Regan • Twin Primes Are Useful
Note. Just another sheet of scratch paper, exploring possible alternatives to the Fourier transforms in the previous post. As a rule, I like to keep Boolean problems in Boolean spaces, partly for aesthetic reasons and partly from a sense that it doesn’t reduce the computational complexity of Boolean problems to replace them with integer or real number problems. I’ll begin by copying the previous post as a template and gradually transform it as I proceed.
Begin with a survey of concrete examples, perhaps in tabular form.
Notation
Boolean domain
Boolean function on variables
Boolean coordinate projections
where such that
Minimal negation operator In contexts where the meaning is clear,
may be written as
or even, using a different style of parentheses, as
For ease of reading formulas, let
Identify with the corresponding singular proposition
Try some other bases, but with addition as in
Observation. The propositions are pairwise orthogonal.
Let I’m thinking of calling these the cosingular or fenestral propositions. (I would have called them the lacunary or umbral propositions but those terms already have established meanings in mathematics.) On third thought, I think I’ll call them crenular propositions, a crenel being a notch at the top of a structure.
Definitions
Fourier coefficient of on
Fourier expansion of
Tables
Notes
References
21 May 2013 | Twin Primes Are Useful |
08 Nov 2012 | The Power Of Guessing |
05 Jan 2011 | Fourier Complexity Of Symmetric Boolean Functions |
19 Nov 2010 | Is Complexity Theory On The Brink? |
18 Sep 2009 | Why Believe That P=NP Is Impossible? |
04 Jun 2009 | The Junta Problem |