Fourier Transforms of Boolean Functions • 1

Posted on May 30, 2013 by Jon Awbrey

Re: R.J. Lipton and K.W. Regan • Twin Primes Are Useful

The problem is concretely about Boolean functions {f} of {k} variables, and seems not to involve prime numbers at all. For any subset {S} of the coordinate [indices], the corresponding Fourier coefficient is given by:

\displaystyle \hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x) \chi_S(x)

where {\chi_S(x)} is {-1} if {\sum_{i \in S} x_i} is odd, and {+1} otherwise.

Note to Self. I need to play around with this concept a while.

Notation (from KLMMV • On the Fourier Spectrum of Symmetric Boolean Functions)

{f : \{0,1\}^k \to \{0,1\}}

{S \subseteq [k] = \{1, \ldots, k\}}

{\chi_S(x) = (-1)^{\sum_{i \in S} x_i}}

The order of a Fourier coefficient {\hat{f}(S)} is {|S|}.

The Fourier expansion of {f} is:

{\displaystyle f(x) = \sum_{S \subseteq [k]} \hat{f}(S) \chi_S(x)}

Added Notation (for shifting between coordinate indices and actual coordinates)

{\mathcal{X} = \{x_1, \ldots, x_k\}}

{\mathcal{S} = \mathcal{X}_S = \{x_i : i \in S\}}

{\boldsymbol{\chi}_\mathcal{S}(x) = \chi_S(x)}

{\hat{f}(\mathcal{S}) = \hat{f}(S)}

Additional Formulas

{\displaystyle \boldsymbol{\chi}_\mathcal{S}(x) = \prod_{x_i \in \mathcal{S}} (-1)^{x_i}}

Begin with a survey of concrete examples, perhaps in tabular form.

{k = 1}

…

{k = 2}

For ease of reading formulas, let {x = (x_1, x_2) = (u, v)}.

Tables

\begin{array}{|c||*{4}{c}|} \multicolumn{5}{c}{\text{Table 2.1. Values of}~ \boldsymbol{\chi}_\mathcal{S}(x)} \\[4pt] \hline \mathcal{S} & (1, 1) & (1, 0) & (0, 1) & (0, 0) \\ \hline\hline \varnothing & +1 & +1 & +1 & +1 \\ \{ u \} & -1 & -1 & +1 & +1 \\ \{ v \} & -1 & +1 & -1 & +1 \\ \{ u, v \} & +1 & -1 & -1 & +1 \\ \hline \end{array}
 

\begin{array}{|*{5}{c|}*{4}{r|}} \multicolumn{9}{c}{\text{Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables}}\\[4pt] \hline \text{~~~~~~~~} & \text{~~~~~~~~} & & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} \\ L_1 & L_2 && L_3 & L_4 & \hat{f}(\varnothing) & \hat{f}(\{u\}) & \hat{f}(\{v\}) & \hat{f}(\{u,v\}) \\ ~&~&~&~&~&~&~&~&~\\ \hline && u = & 1~1~0~0 &&&&& \\ && v = & 1~0~1~0 &&&&& \\ \hline f_{0} & f_{0000} && 0~0~0~0 & (~) & 0 & 0 & 0 & 0 \\ f_{1} & f_{0001} && 0~0~0~1 & (u)(v) & 1/4 & 1/4 & 1/4 & 1/4 \\ f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1/4 & 1/4 &-1/4 &-1/4 \\ f_{3} & f_{0011} && 0~0~1~1 & (u) & 1/2 & 1/2 & 0 & 0 \\ f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1/4 &-1/4 & 1/4 &-1/4 \\ f_{5} & f_{0101} && 0~1~0~1 & (v) & 1/2 & 0 & 1/2 & 0 \\ f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 1/2 & 0 & 0 &-1/2 \\ f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 3/4 & 1/4 & 1/4 &-1/4 \\ \hline f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 1/4 &-1/4 &-1/4 & 1/4 \\ f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1/2 & 0 & 0 & 1/2 \\ f_{10}& f_{1010} && 1~0~1~0 & v & 1/2 & 0 &-1/2 & 0 \\ f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 3/4 & 1/4 &-1/4 & 1/4 \\ f_{12}& f_{1100} && 1~1~0~0 & u & 1/2 &-1/2 & 0 & 0 \\ f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 3/4 &-1/4 & 1/4 & 1/4 \\ f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 3/4 &-1/4 &-1/4 &-1/4 \\ f_{15}& f_{1111} && 1~1~1~1 & ((~)) & 1 & 0 & 0 & 0 \\ \hline \end{array}
 

\begin{array}{|*{5}{c|}*{4}{r|}} \multicolumn{9}{c}{\text{Table 2.3. Fourier Coefficients of Boolean Functions on Two Variables}}\\[4pt] \hline \text{~~~~~~~~} & \text{~~~~~~~~} & & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~} & \text{~~~~~~~~~} \\ L_1 & L_2 && L_3 & L_4 & \hat{f}(\varnothing) & \hat{f}(\{u\}) & \hat{f}(\{v\}) & \hat{f}(\{u,v\}) \\ ~&~&~&~&~&~&~&~&~\\ \hline && u = & 1~1~0~0 &&&&& \\ && v = & 1~0~1~0 &&&&& \\ \hline f_{0} & f_{0000} && 0~0~0~0 & (~) & 0 & 0 & 0 & 0 \\ \hline f_{1} & f_{0001} && 0~0~0~1 & (u)(v) & 1/4 & 1/4 & 1/4 & 1/4 \\ f_{2} & f_{0010} && 0~0~1~0 & (u)~v~ & 1/4 & 1/4 &-1/4 &-1/4 \\ f_{4} & f_{0100} && 0~1~0~0 & ~u~(v) & 1/4 &-1/4 & 1/4 &-1/4 \\ f_{8} & f_{1000} && 1~0~0~0 & ~u~~v~ & 1/4 &-1/4 &-1/4 & 1/4 \\ \hline f_{3} & f_{0011} && 0~0~1~1 & (u) & 1/2 & 1/2 & 0 & 0 \\ f_{12}& f_{1100} && 1~1~0~0 & u & 1/2 &-1/2 & 0 & 0 \\ \hline f_{6} & f_{0110} && 0~1~1~0 & (u,~v) & 1/2 & 0 & 0 &-1/2 \\ f_{9} & f_{1001} && 1~0~0~1 &((u,~v))& 1/2 & 0 & 0 & 1/2 \\ \hline f_{5} & f_{0101} && 0~1~0~1 & (v) & 1/2 & 0 & 1/2 & 0 \\ f_{10}& f_{1010} && 1~0~1~0 & v & 1/2 & 0 &-1/2 & 0 \\ \hline f_{7} & f_{0111} && 0~1~1~1 & (u~~v) & 3/4 & 1/4 & 1/4 &-1/4 \\ f_{11}& f_{1011} && 1~0~1~1 &(~u~(v))& 3/4 & 1/4 &-1/4 & 1/4 \\ f_{13}& f_{1101} && 1~1~0~1 &((u)~v~)& 3/4 &-1/4 & 1/4 & 1/4 \\ f_{14}& f_{1110} && 1~1~1~0 &((u)(v))& 3/4 &-1/4 &-1/4 &-1/4 \\ \hline f_{15}& f_{1111} && 1~1~1~1 & ((~)) & 1 & 0 & 0 & 0 \\ \hline \end{array}

To be continued …

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
Posted in Boolean Functions, Computational Complexity, Fourier Transforms, Harmonic Analysis, Logic, Mathematics, Propositional Calculus | Tagged , , , , , , | 1 Comment

Strangers In Paradise

Posted on May 22, 2013 by Jon Awbrey

Re: Kilvington’s Sophismata

Comment 1

On the one hand Aristotle gives us the logic of analogy (παραδειγμα).  On the other hand he cautions us that different paradigms may have no common measure.  It seems these Immortals are always getting ahead of their time❢

Comment 2

How much drama in Plato’s Heaven when Heraclitus and Parmenides are reconciled❢

Or does it trail off to the anticlimax that Sisyphus gradually wears down the mountain?

Comment 3

Dealing with qualitative change in logical terms has long been of interest to me.  It became a hot topic in Artificial Intelligence Research during the 1980s — work by Ben Kuipers and Ken Forbus especially comes to mind.  Many of the settings where I worked at the time required me to find bridges between qualitative (logical) and quantitative (statistical) research methods.  I recall describing my efforts in that vein to one of my Master’s thesis advisers under the following rubric.

  • Approaching a Qualitative Theory of Differential Equations (QTDE)
    By Means of a Differential Theory of Qualitative Equations (DTQE)

Another slogan for the approach might as follows.

  • Exchanging a Change of Quality (CQ) for a Quality of Change (QC)

Here’s another piece I wrote in that line:

Posted in Albert Camus, Analogy, Aristotle, Differential Logic, Eleatic Stranger, Heraclitus, Incommensurability, Logic, Metabasis, Paradigmata, Paradox, Parmenides, Plato, Richard Kilvington, Sisyphus, Sophismata, Thomas Kuhn, Zeno | Tagged , , , , , , , , , , , , , , , , , | Leave a comment

⚠ It’s A Trap ⚠

Posted on May 18, 2013 by Jon Awbrey

Re: Kenneth W. Regan • Graduate Student Traps

The most common mathematical trap I run across has to do with Triadic Relation Irreducibility, as noted and treated by the polymath C.S. Peirce.

This trap lies in the mistaken belief that every 3-place (triadic or ternary) relation can be analyzed purely in terms of 2-place (dyadic or binary) relations — “purely” here meaning without resorting to any 3-place relations in the process.

A notable thinker who not only fell but led many others into this trap is none other than René Descartes, whose problematic maxim I noted in the following post.

As mathematical traps go, this one is hydra-headed.

I don’t know if it’s possible to put a prior restraint on the varieties of relational reduction that might be considered, but usually we are talking about either one of two types of reducibility.

Compositional Reducibility.  All triadic relations are irreducible under relational composition, since the composition of two dyadic relations is a dyadic relation, by the definition of relational composition.

Projective Reducibility.  Consider the projections of a triadic relation L \subseteq X \times Y \times Z on the 3 coordinate planes X \times Y, ~ X \times Z, ~ Y \times Z and ask whether these dyadic relations uniquely determine L.  If so, we say L is projectively reducible, otherwise it is projectively irreducible.

Et Sic Deinceps …

  • More Discussion of Relation Reduction • OEIS Wiki • PlanetMath
  • Previous Posts on Triadic Relation Irreducibility • (1) • (2) • (3)
Posted in C.S. Peirce, Category Theory, Descartes, Error, Fallibility, Logic, Logic of Relatives, Mathematical Traps, Mathematics, Peirce, Pragmatism, Reductionism, Relation Theory, Semiotics, Sign Relations, Triadic Relations | Tagged , , , , , , , , , , , , , , , | 5 Comments

Triadic Relation Irreducibility • 3

Posted on May 16, 2013 by Jon Awbrey

References

Related Readings

Posted in C.S. Peirce, Category Theory, Inquiry, Logic, Logic of Relatives, Mathematics, Peirce, Pragmatism, Relation Theory, Semiosis, Semiotics, Sign Relational Manifolds, Sign Relations, Teridentity, Thirdness, Triadic Relations | Tagged , , , , , , , , , , , , , , , | 1 Comment

grabitational singularity

Posted on May 16, 2013 by Jon Awbrey
the trouble with a bubble
on a pyramid top
is the point
when it
pop
⚠
⚠⚠
⚠⚠⚠
⚠⚠⚠⚠
⚠⚠⚠⚠⚠
⚠⚠⚠⚠⚠⚠
Posted in Grabitational Singularity, Singularity, Verse | Tagged , , | 2 Comments

What part do arguments from authority play in mathematical reasoning?

Posted on May 14, 2013 by Jon Awbrey

In forming your answer you may choose to address any or all of the following aspects of the question:

Descriptive
What part do arguments from authority actually play in mathematical reasoning?
Normative
What part do arguments from authority ideally play in mathematical reasoning?
Regulative
What if any discrepancies exist between the actual and the ideal?
What if anything should be done about the discrepancies that exist?

Recycled from a question I asked on MathOverFlow.

Posted in Artificial Intelligence, Authority, Control, Control Theory, Cybernetics, Fixation of Belief, History of Mathematics, History of Science, Information, Information Theory, Inquiry, Inquiry Driven Systems, Intelligent Systems, Intuition, Logic, Logic of Science, Mathematical Intuition, Mathematical Reasoning, Operations Research, Optimal Control, Optimization, Philosophy of Science, Scientific Method | Tagged , , , , , , , , , , , , , , , , , , , , , , | 2 Comments

C.S. Peirce : Information = Comprehension × Extension

Posted on May 8, 2013 by Jon Awbrey

Re: R.J. Lipton and K.W. Regan • A Most Perplexing Mystery

The inverse relationship between symmetry and diversity — that we see for example in the lattice-inverting map of a Galois correspondence — is a variation on an old theme in logic called the “inverse proportionality of comprehension and extension”.

C.S. Peirce, in his probings of the “laws of information”, found this principle to be a special case of a more general formula, saying that the reciprocal relation holds only when the quantity of information is constant.

Readings

Posted in C.S. Peirce, Comprehension, Diversity, Extension, Information, Information = Comprehension × Extension, Inquiry, Intension, Logic, Logic of Science, Peirce, Reciprocity, Semiotics, Sign Relations, Symmetry, Variety | Tagged , , , , , , , , , , , , , , , | 13 Comments

Rock On

Posted on May 6, 2013 by Jon Awbrey
Elsewhere I have brought out the fact that human will had no other purpose than to maintain awareness.  But that could not do without discipline.  Of all the schools of patience and lucidity, creation is the most effective.  It is also the staggering evidence of man’s sole dignity:  the dogged revolt against his condition, perseverance in an effort considered sterile.  It calls for a daily effort, self-mastery, a precise estimate of the limits of truth, measure, and strength.  It constitutes an ascesis.  All that “for nothing”, in order to repeat and mark time.  But perhaps the great work of art has less importance in itself than in the ordeal it demands of a man and the opportunity it provides him of overcoming his phantoms and approaching a little closer to his naked reality. (115)
⁂  
All that remains is a fate whose outcome alone is fatal.  Outside of that single fatality of death, everything, joy or happiness, is liberty.  A world remains of which man is the sole master.  What bound him was the illusion of another world.  The outcome of his thought, ceasing to be renunciatory, flowers in images.  It frolics — in myths, to be sure, but myths with no other depth than that of human suffering and, like it, inexhaustible.  Not the divine fable that amuses and blinds, but the terrestrial face, gesture, and drama in which are summed up a difficult wisdom and an ephemeral passion. (117–118)
⁂  
I leave Sisyphus at the foot of the mountain!  One always finds one’s burden again.  But Sisyphus teaches the higher fidelity that negates the gods and raises rocks.  He too concludes that all is well.  This universe henceforth without a master seems to him neither sterile nor futile.  Each atom of that stone, each mineral flake of that night-filled mountain, in itself forms a world.  The struggle itself toward the heights is enough to fill a man’s heart.  One must imagine Sisyphus happy. (123)

Albert Camus, The Myth of Sisyphus and Other Essays, Justin O’Brien (trans.), Random House, New York, NY, 1991.  Originally published in France as Le Mythe de Sisyphe by Librairie Gallimard, 1942.  First published in the United States by Alfred A. Knopf, 1955.

Posted in Absurdity, Albert Camus, Diversity, Existentialism, Freedom, Myth, Oedipus, Passion, Revolt, Sisyphus | Tagged , , , , , , , , , | 14 Comments

Finding a Needle in a Cactus Patch

Posted on April 30, 2013 by Jon Awbrey

Re: R.J. Lipton • Sex, Lies, And Quantum Computers

Don’t know much about quantum computation, but my ventures in graphical syntaxes for propositional calculus did turn up a logical operator whose evaluation process reminded me a little of the themes involved in the collapse of the wave function.

Here is the essential information —

Boolean formulas constructed from minimal negation operators can be given graph-theoretic representation as “decorated” or “painted” versions of rooted cactus graphs.

Here are a couple of places where you can see some pictures and a description of the Fundamental Evaluation Rule for cactus expressions of propositional formulas.

Posted in Boolean Functions, C.S. Peirce, Cactus Graphs, Computational Complexity, Graph Theory, Logic, Logical Graphs, Minimal Negation Operators, Painted Cacti, Peirce, Propositional Calculus, Quantum Computing, Semiotics | Tagged , , , , , , , , , , , , | 4 Comments

Revolt, Freedom, Passion

Posted on April 23, 2013 by Jon Awbrey
Thus I draw from the absurd three consequences, which are my revolt, my freedom, and my passion. By the mere activity of consciousness I transform into a rule of life what was an invitation to death — and I refuse suicide. I know, to be sure, the dull resonance that vibrates throughout these days. Yet I have but a word to say: that it is necessary. When Nietzsche writes: “It clearly seems that the chief thing in heaven and on earth is to obey at length and in a single direction: in the long run there results something for which it is worth the trouble of living on this earth as, for example, virtue, art, music, the dance, reason, the mind — something that transfigures, something delicate, mad, or divine,” he elucidates the rule of a really distinguished code of ethics. But he also points the way of the absurd man. Obeying the flame is both the easiest and the hardest thing to do. However, it is good for man to judge himself occasionally. He is alone in being able to do so. (64–65)

Albert Camus, The Myth of Sisyphus and Other Essays, Justin O’Brien (trans.), Random House, New York, NY, 1991. Originally published in France as Le Mythe de Sisyphe by Librairie Gallimard, 1942. First published in the United States by Alfred A. Knopf, 1955.

Posted in Absurdity, Albert Camus, Existentialism, Freedom, Inquiry, Method, Nietzsche, Passion, Revolt, Sisyphus | Tagged , , , , , , , , , | 3 Comments