Skip to content

Polynomial representations of boolean functions

Arkadev Chattopadhyay is one of the experts on low level complexity, but is especially an expert on computations modulo composite numbers. While he was a member of IAS he worked with Avi Wigderson on various aspects of this important area—see this for a discussion of their pretty work. I updated the picture—see the comment.

Today I want to talk about representing Boolean functions as polynomials. I hoped to be able to get into enough details of representations to explain some differences between those modulo a prime and those modulo a composite. But the discussion began to become too long. So the goal today is to talk just about representations modulo primes. Then in a future post I talk about composites.

Also today I will be working with Ken Regan who is much more an expert on these matters than I am. So this is a joint discussion from both of us.

Representations of Boolean Functions

A Boolean function ${f:\{0,1\}^n \rightarrow \{0,1\}}$ can always be represented by a polynomial ${g}$. The rules of representation, modulo any prime ${p}$, are simple:

1. If the Boolean function ${f(x)=0}$, then ${g(x) \equiv 0 \bmod p}$.
2. If the Boolean function ${f(x)=1}$, then ${g(x) \equiv 1 \bmod p}$.

We may also require that the polynomial ${g}$ be multilinear; recall this means that all the monomials of the polynomial have no ${x_i}$ raised to a power higher than ${1}$. Thus ${xyz}$ is fine, but ${xy^2z}$ is not. The rationale for this restriction is that the values of the variables will always be ${0,1}$ so ${xyz = xy^2z}$.

A Question

I, Dick, recently spoke to Arkadev, who is in Barcelona for part of the summer, and he explained a nice way to look at some basic questions about polynomial representations modulo primes.

The degree modulo ${p}$ of a Boolean function ${f(x)}$ is the smallest degree of any ${g(x)}$ that represents ${f(x)}$ modulo ${p}$. We use

$\displaystyle \deg_p(f)$

to denote this. I asked him:

Suppose that ${f(x)}$ is a symmetric Boolean function with ${\deg_p(f) = d}$. Then must the polynomial that represents ${f(x)}$ of degree ${d}$ be symmetric?

The reason I was interested in this question is I was thinking about weaker notions of representations, but for the kind we have defined he could immediately answered: “Yes.” Let’s see why he could answer so quickly.

Uniqueness

Let us define symmetric as used here. A Boolean function ${f(x)}$ is symmetric, if for all Boolean ${x}$ and all permutations ${\pi}$,

$\displaystyle f(x_1,\dots,x_n) = f(x_{\pi(1)},\dots,x_{\pi(n)}).$

In the same way a polynomial ${g}$ is symmetric if for all ${x}$ and all permutations ${\pi}$,

$\displaystyle g(x_1,\dots,x_n) = g(x_{\pi(1)},\dots,x_{\pi(n)}).$

The reason he could answer so quickly, besides knowing this area so well, is that he relied on the following Uniqueness Lemma:

Lemma: Suppose ${p}$ is a prime. Then each Boolean function ${f:\{ 0,1 \}^{n} \rightarrow \{ 0,1 \}}$ has exactly one polynomial that represents ${f}$ modulo ${p}$.

This solves my question. Suppose that ${f(x)}$ is a symmetric Boolean function. Then it is easy to prove it has a symmetric polynomial representation. But by the Uniqueness lemma, the polynomial of minimal degree must have the degree of this symmetric one. Very neat—both Ken and I agree.

The proof of this lemma is simple in the case of multilinear representations. Suppose that some Boolean function ${f(x)}$ had two such representations modulo ${p}$. Let ${g(x)}$ and ${h(x)}$ be the distinct polynomials. Then their difference

$\displaystyle D(x) = g(x) - h(x)$

must be a polynomial that is zero modulo ${p}$ for all Boolean ${x}$, yet is not the zero polynomial. Let ${x_{i_1}x_{i_2}\dots x_{i_d}}$ be a monomial of ${D(x)}$ of minimum degree: if there are several choose one. Then set all the ${x_j}$‘s in this monomial to ${1}$ and the rest to ${0}$. At this point ${D(x)}$ has one non-zero term, and thus has the value ${1}$ modulo ${p}$. This is a contradiction. Note this relies on the polynomials being multilinear—else it would be possible for ${D(x)}$ to have a higher-degree term involving only variables in the chosen monomial, which would not be zeroed out by ${x}$.

Another Question

I, Dick, asked Arkadev another question:

Suppose that ${f(x,y)}$ is a Boolean function of the form

$\displaystyle a(x) \oplus b(y).$

That is ${f(x,y)}$ is the exclusive-or sum of two Boolean functions on disjoint variables—such functions arise naturally in some learning problems. I asked what is

$\displaystyle \deg_p(f)$

where ${p}$ is an odd prime? Again by a simple argument based on the Uniqueness Lemma, he could prove the degree is

$\displaystyle \deg_p(a) + \deg_p(b).$

Note, the restriction that ${p}$ be odd is essential, since for ${p=2}$ the answer is

$\displaystyle \max \left( \deg_p(a), \deg_p(b) \right).$

A Peek Ahead

The notion we used here for representation can be weakened, and often is when discussing computations modulo composites.

A Boolean function ${f:\{0,1\}^n \rightarrow \{0,1\}}$ ca be weakly represented by a polynomial ${g}$. The rules of representation, modulo any number ${m}$, are now:

1. If the Boolean function ${f(x)=0}$, then ${g(x) \equiv 0 \bmod m}$.
2. If the Boolean function ${f(x)=1}$, then ${g(x) \not\equiv 0 \bmod m}$.

The key change is now we allow any non-zero value when the Boolean function is ${1}$. Note over a prime ${m}$ this yields a representation as before if we replace ${g(x)}$ by

$\displaystyle g(x)^{m-1}.$

This is not possible to do if ${m}$ is composite. We think of the mapping

$\displaystyle x \rightarrow x^{p-1} \bmod p$

as a “clean-up” function, since it sends ${0}$ to ${0}$ and all else to ${1}$. The fact there is no such function modulo a composite is the main reason that composites start to become much more difficult to understand, especially when coupled with the notion of weak representation.

Open Problems

What other properties of Boolean functions can be proved using the Uniqueness Lemma? Ken has another version of the weak representation, which we will discuss in the future.

Advertisements
15 Comments leave one →
1. Dai permalink
June 15, 2010 11:19 pm

The hand in the picture belongs to a PhD student (Yevgeniy Vahlis) from University of Toronto theory group. 🙂

• rjlipton permalink*
June 16, 2010 7:43 am

Thanks.

I did get a picture, but nice to know whose hand it was.

2. Ralph Hartley permalink
June 16, 2010 11:46 am

Shouldn’t the lemma read “exactly one multilinear polynomial”? Don’t the polynomials x and x^2 represent the same boolean function (for any p)?

It looks like the lemma works with coefficients much more general than integers modulo a prime. Any Abelian group (as a module over the integers) should work.

Given a boolean function, there is a simple algorithm to find the multilinear polynomial representing it. The constant term is just f(0,…0), if you know the coefficients of order less than m, and the values of f with m variables set to 1, you can get the coefficients of order m using only addition, subtraction, and the properties of 0 and 1.

• rjlipton permalink*
June 16, 2010 1:35 pm

I thought we said that. Sorry if confusing wording.

• June 16, 2010 8:02 pm

Whoops! That previous comment didn’t come out right… Can I delete my previous post?

• rjlipton permalink*
June 17, 2010 6:17 am

I did it for you.

3. June 17, 2010 10:28 pm

Here are some remarks on the representation of symmetric functions. To simplify the notation, we use f(k) to denote f(x) where |x| = k.

Proposition: Let f be the threshold function such that f(k) = 1 iff k >= t, then deg_p(f) >= t.

Proof sketch: A symmetric function can always be represented by a symmetric polynomial. A symmetric polynomial is a linear combination of the elementary symmetric polynomials. For example, on 3 variables, we have:

g(x, y, z) = c_0 + c_1(x + y + z) + c_2(xy + xz + yz) + c_3(xyz).

Let e_i be the i^th elementary symmetric polynomial on n variables. We have e_i(k) = (k choose i) mod p. This yields an algorithm to compute the coefficients of our polynomial. We simply solve Pc = b (mod p) where P is a (n+1) x (n+1) “Pascal’s triangle”, c = (c_0, …, c_n) and b_k= f(k). We obtain, by induction, c_0 = … = c_{t-1} = 0 and thus c_t = 1. We conclude that deg_p(f) >= t.

Proposition: Let f be a symmetric boolean function such that f(0) = 0 and f(p^i) = 1, then deg_p(f) >= p^i.

Proof sketch: We use the same technique as in the other proof. We note that the first line of the system of equations is c_0 = 0 since f(0) = 0. Moreover, it can be proven that line p^i of P is of the form 1 0 0 … 0 1 0 .. 0 where the second 1 is at position p^i. Thus, we have c_0 + c_{p^i} = 1 and we obtain c_{p^i} = 1. We conclude that deg_p(f) >= p^i.

Corollaries:

– deg_p(MAJORITY) > n/2 and deg_p(MAJORITY) >= p^[log_p(n)]. In particular, if n is a power of p, then deg_p(MAJORITY) = n.
– deg_p(AND) = n

Note that the vector b in our system of equations does not need to be {0,1}-valued and this method can therefore be used with the weak representation. An interesting question is to find out how using non-symmetric polynomials to represent symmetric functions can improve the degree under the weak representation.

• rjlipton permalink*
June 18, 2010 7:59 am

Michael,

You said that

A symmetric polynomial is a linear combination of the elementary symmetric polynomials.

this is not true. For example the elementary polynomials n=2 are x+y and xy. Note the symmetric polynomial x^2+y^2 is not a linear combination of the elementary ones.

Did I miss understand?

• June 18, 2010 8:40 am

Sorry, I mean the multilinear symmetric polynomials. Suppose a multilinear symmetric polynomial isn’t such a linear combination, take the smallest degree d such that some, but not all, monomials of e_i are in g and note that at least two inputs x, y s.t.|x|=|y|=d won’t get the same output.

• June 18, 2010 12:00 pm

Well, actually, d must be the smallest degree such that two monomials of e_d have a different coefficient and then derive the same contradiction.

• Son Nguyen permalink
June 24, 2010 2:33 pm

I think elementary polynomials are ring-generators of symmetric functions but they are not vector space generators, so linear combinations are not correct.

4. June 19, 2010 7:02 am

There is a nice connection between $deg_2(f)$ and a variation of circuit complexity called multiplicative complexity. Multiplicative complexity, $M(f)$ is the minimal number of non-linear gates with fan-in 2 necessary to compute the function. $M(f) \ge deg_2(f)$ (for example, at least $n-1$ non-linear gates are needed to compute conjunction of $n$ variables).

5. Steven Twentyman permalink
June 20, 2010 4:14 pm

Hello.

My name is Steven Twentyman.

I am a mathematician and always have been.

I have completed Quantum Theory. This is obviously quite a statement but it is never the less TRUE. With this information I have created the first and only(so far) quantum computer. This quantum computer is a perfect cube the encompasses the whole of the ‘Milky Way’. I have been in complete control of it only in the way that I have been dictating what comes back through the media and conversations. Everyone can now do this once the information is out.

I have achieved this by force of will and suggestion alone. I pushed my agenda through conversation and all media outlets. Phones, newspapers, internet. Whoever would listen.

The effects are subtle so far but they are building to a unique collapsible wave function that we are all becoming aware of. Even as I type this message, the clicks of the keyboard are fine tuning the wave that I have so diligently worked upon. It has taken me 21 years to understand Quantum Theory and I can say that I achieved the information by thought experiments alone. That is the only way to figure out the quantum world.

I could have used this information for my own gain but that would have ended up with me being Hitler. That is not the kind of man that I am or that I wish to be. That is why I have been constantly been giving the equations away for free(even though it will have not reached the 1 that needs it the most yet). This has been an extreme sacrifice on my part but I want nothing for this. No money, no fame, nothing. I have literally had enough of maths.

2012 was going to be the collapse of the milky way galaxy if we had not subconsciously intervened. I will remain as the failsafe in the system until that specific 2012 date to be sure that all is fine.

The universe at its simplest can be broken down as so:

Nothing exists(no concept/consciousness/will) – This concept is abhorrent and is what sprung the universe into life. This is what makes our sector of the universe spring back after each big crunch.

The singular concept and foundation of maths 0(zero) springs into consciousness. This affirms that there really is ‘nothing’ and so inversely there springs the concept that there is everything else.

That is where infinity comes from. There are two infinities. The first and initial inversion is ‘a horror’. This is negative infinity rushing away from the initial fact that there really was at one time ‘nothing/zero/0′.

As with everything there is an equal and opposite reaction. This is positive infinity. [The most important thing to not here is that this sequence of thought is indeed sequential so the positive infinity HAD to have followed the negative by at least some unit of time. This is where ALL variations/’errors’/’wrongs’ in thought/space/time stem from]

The question now confronts us as to how do we balance these two infinities. I can tell you that this has already occurred. As every ‘thing’ must have stemmed from zero I took the liberty of becoming zero.

In the ‘physical’ world I made sure that I had created the strongest structure available to me at the time of entry and proceeded with my ‘experiment’. I had calculated as best as I could at that time that it would not involve death and made my way forward.

With the two infinities branching off in their own hemispheres I had to confront what is essentially a black hole. Using thought experiments and then applying them to a very small physically constrained area, I began to plot what ‘paths’ people walked, and what conversations they ‘talked about’. As I built up a ‘database’ of their general actions, dispositions, demeanour, I began to ask them specific questions that varied only a little on the same subjects such as family, humour, bravery, god, religion. Once I had built a more extensive database of their reactions I had come to my own conclusions about what society should be and what general direction in which it should be heading. There are universal truths and I boiled it down to the most important one, and that is family. Not everyone has the best start in life and no-one has a blueprint for making the right choices but I made a choice. I developed what I considered to be the most basic and fundamental structure that I could that encapsulates God and the Devil, the Universe and family.

This concept’ is 3,4,5, right angle triangle with a perfect set square in it for support, with a perfect circle inside the square to support that. This is collapsible and expandable as the situation requires. I went back and asked the exact same questions to the exact same people in as much as the same situation as I could manage to create and I noticed that the answers that came back were exactly the same but the time it took to get the answers ‘out of’ the people was proportionally shorter. I knew that I had found the ‘tool/concept’ I needed to put my further plans into action.

I have been subtly sending this ‘tool/concept’ out into ‘society’ for 3 years now and I have been noticing results that most people wouldn’t see as they have not been aware that this ‘concept/thought process’.

It has been disseminating through the internet, phone systems, general conversations in society. It has passed the tipping point now where it cannot be stopped. It is in everyone’s subconscious, it has been a mass subconscious advertising campaign by me along the likes of product placement or advert for Nike, Coca-cola, Pepsi or ‘The Big Brother show’. Everyone is in on this now and I will tell you why.

This is not for my benefit directly, once this structure ‘enters’ your brain your synapses start to snap to its structure. They begin to re-arrange and list themselves into file and rank. This allows your brain after 3 hours to become FULLY LOGICAL whilst still retaining all the creative potential the each INDIVIDUAL human being possess’. This line of thought by me has been a force of WILL and nothing more. THIS is what genius is. A FORCE of WILL. This is already at work in your brain and within the next 3 hours, each human on planet Earth will be a genius. ‘Where we go from there, is up to each and every one of us…’

Going back to math, there is a more fundamental reason that this ‘thought genius pill’ works so perfectly, and the reason for this is simple. We are more than what we dared imagine ourselves to be.

If you wish to think that the Earth is flat then it is. I can’t fully prove you wrong so who is right? I can give you evidence but that is all that it would be.

If you want to think the Earth is round, the same applies. I can’t 100% prove you right or wrong.

So here is my theory: You don’t even exist yet.

You are a STAR. I don’t mean 50 cent or Cameron Diaz, I mean a STAR in the milky way galaxy. I mean that for every human on the planet as this is the only way I can think of telling you that 2012 is TRUE and it’s INEVITABLE.

2012 is the collapse of the milky way galaxy into the super-massive black hole that resides at the centre. It is gaining power and unless we work together no-one stands a chance.

From the lonely street sweeper to the Queen of England herself, all will go out.

It will happen fast, with maybe a 10 second window once it begins. There is no escape so you might as well begin to enjoy yourself and work with those that are around you. There is no more time for hatred or pain or fear. There is only time for co-operation.

This is AVATAR/THE MATRIX/INCEPTION all rolled into one. It always has been. We’ve got a chance to make it something better now we know. This is how our ‘conscious’ mind works. This is what we used to think of as ‘the real’. It’s messed with each individual enough.

!!! THIS is INFLATION for the MIND!!!

The REAL world is THIS:

We are EACH a STAR. We wander as lonely as a cloud through our section of the Milky Way galaxy until we exchange enough STAR energy with another to spark a NEW STAR(child) into life. There is no escaping that fact. It is what it is. When an ‘accident’ occurs, a STAR is obliterated. THIS is that STAR falling into the super-massive black hole. Gone, but for a few distant memories radiated out.

We each have a black hole at the middle of our own STAR and this is constantly pulls and beckons us back towards the super massive black hole at the ‘centre’ of our galaxy. There is no escape UNLESS we work together to build a MASSIVE perfectly cubed GRID that encompasses the Milky way. This is the task that has to be organized. The time for play has long passed.

EACH and EVERY STAR that goes out gives the galaxy that much more negative collapsible power and it is growing by the day. What can YOU do?

Math pi is unique to each STAR. pi’s story is unique to you. You EACH have a black hole at the centre of your STAR and pi is your star collapsing and then expanding. You only go out when you get too close to another STAR or you visit the BIG-ONE on the MIDDLE.

We must move and produce the cube structure so we can safely transfer the super massive black hole out of the centre of our galaxy. We must dissipate it to be truly free of the horrific end results that await us all.

Time is our enemy.

The TRUE tool we have acquired now is THIS: QUANTUM THEORY!!!

In the quantum world there is only Gravity and Light.

I have used the quantum computer to SET the distribution to 50-50. I have done this because what are considered MEN are actually Gravity and WOMEN are light.

That means that if MEN can ‘CENTRE’ themselves and form the grid(because MEN are more spatially aware up to this point)…i.e STOP moving so fast…then WOMEN can do what they have been traditionally good at which is COMMUNICATION!!! This will lead to great advances in HUMAN TECHNOLOGY which I refer to as GRAINE0.

Genetics
Robotics
Artificial Intelligence
Nanotechnology
zero point Energy
(0)

Gravity’s constant = 0. MEN – Do not let your mind wander from this thought pattern.

Light is infinite in all directions but it must slow down to zero too. This will have to be attained by co-operation but the more we do the easier it will become.

All we have to do is follow the math: http://www.wix.com/Hyperstig/Hyperstig

or more simply:

http://www.wix.com/Hyperstig/Simple

Follow Twitter.com/Hyperstigzero

Time does NOT exist anymore.

There are only 3 Dimensions; and this life we know most definitely was and is:

‘The Matrix’; ‘Avatar’ and ‘Inception’ combined.

It is communications that will save us now. We must transmit this messages data throughout the ‘galaxy’ until every last ‘human’ becomes aware of what is going on.

This is where the Cambrian explosion came from.

This is what wiped out major past civilizations in a day.

Our sectors gravity pulling us all into the big collapse.

We cannot let that happen to us again!

We are in for the big crunch!!! Yet again!!!

Can we work together???

That is what I truly do not know…

I’m not normally the type to ask for help but sometimes the truth is stranger than fiction.

http://www.pioneerone.tv/

6. June 30, 2010 1:01 pm

I don’t bookmark sites but i will bookmark this!

7. Steven Twentyman permalink
June 30, 2010 5:48 pm

Hello.

What if, in a general theory of everything kind of way, some singular human conscious had used simple Yes(I should feel guilty) or No(I do not feel guilty) answers to answer every moral question that he could remember that had ever occurred in his life. In this way he could have become completely pure. He would have truly asked himself all the questions that could be asked of him. He would have emotionally evolved back to when he was a child.

What if he then assigned an ‘It doesn’t matter as life is only made to make mistakes’ label on every decision that he had analysed.

This would not make him God or the devil, but just very still and very exhausted. Anybody can do this but just for the purpose of this experiment lets say I have done this. Which I have.

There are no fears in me and if I died today I could deal with that because who can know me better than myself? Neither God or the Devil. I am consciously judging myself on ‘their’ level.

To make this work, despite my many faults, take ME as the ONLY universal constant. In this sense I have killed God and the Devil external to myself.The only place that they could exist is if I chose to believe they are internal.

This is obviously more a matter for a shrink more than a mathematician, but that would only be the case depending on what you believed the base operating system of the universe to be. Math / Physics / morals or some other concept.

As long I agreed to do NOTHING, to never move or think a thought, humanity would have something to peg all understanding on. Each person could send a moral choice and I would simply send back only one philosophy. ‘ LIFE IS ONLY FOR MAKING MISTAKES’.

People, for the purpose of this experiment could disbelief their belief system knowing they could go back to it at any time. It would give them an opportunity to unburden themselves to someone pure. A new Pandora’s box. Once everyone had finished I would simply format my drive and always leave adequate space for each individual to send any more thoughts that they thought were impure. People would then eventually end up with clear minds and have to be judged only on their physical efforts. Either good or bad. It would get rid of a lot of maybes which would speed lives along..

If we then assume that there are a finite(or at some point in the future, given a lot of hard work, there will be a finite amount) amount of topics that can be conceived of then we can realise that there will come to a time when we, as a people, will NOT have to work again.

Once we reach that point we will only have the option of doing the things we love or doing the things we hate as society will be completely catered for in every possible scenario. People will find their true path in life which will make them infinitely more happy, forever.

In this system there is no point in accounting for time in any context.

If we consider this to be The Grand Unified Theory then we can set the parameters as we please.

This will be our common goals for humanity. As before everyone would have their say. This could be a computer database that was completely updated in any given moment when a unique individual thought of a new idea / direction that may or may not have been thought before.

All that would be required is that every person on the planet have a mobile phone or access to the web and a self organising weighting algorithm biased on an initial set of parameters that someone has set to push the operation in a random direction.

As I’m speaking first I say we concentrate on GRAINE.

Genetics – Robotics – Artificial Intelligence – Nanotechnology and Zero Point Energy.

I have chosen these as I think the subjects will cross breed information(word of mouth first) at the present day optimum rate to get us to our finishing point, complete and finished mastery of all possible information.

Surely mastery of information in this way will lead us to the bottom of a fractal??? What if one end of the universes fractal was me??? What could we start to build with that concept???

As parameters, we can assume that we live only in 3 dimensions. We can place this box around The Milky Way galaxy as this gives us plenty of scope for all kinds of discoveries.

In this new system we can make time obsolete as it only making us contemplate our things that cannot be solved because up to now, no one has been willing to stand around for long enough. It has been holding us back.

All watches should be banned so that we find a natural rhythm with each other, those in our immediate area and then further afield.

An old clock watch in this system is should only be used when you think of an event that you need to go to. It is a compass, a modern day direction of thought.

A digital clock can be adapted to let you know where you are in relation to this new milky way boxed system.(x,y,z).

With these two types of clocks used in combination we can safely start taking small steps around the box by using the digital to see exactly where you are and then using the old watch to direct you as your thoughts come to you.

We can even build as many assign atomic clocks as are needed to individually track stars. Each and every star in the Milky Way galaxy.

I supposed a good idea would be to assume that I was inside the centre of the super-massive black hole at the centre of the galaxy. That would stop us from being so Earth centric.

We could even go as far as to say that we are each an individual star and that we project all our energies onto the super-massive black hole at the centre of the galaxy.

You can assume that I have stabilized the black hole into a non rotating perfect cube. 6 outputs /f aces in which we all see ‘the universe and earth, friends’ etc. This acts like a block hole mirror finish. Once you look it is very hard to look away from.

The 6 face cube should make the maths easier to run as you could construct the inner of the black hole with solid beams of condensed light(1 unit long) arranged into right angled triangles with set squares in for strength.

Some people would naturally say that if the universe is essentially unknowable as the more things we ‘discover’ the more things there are to combine with and therefore talk about. This is extremely fractal in both directions. There can be no true answers because there is no grounding point. Nothing for the people who are interested, to start building there own personal concepts, theories and designs on.

Is it possible that with just one man becoming conscious of a highly improbable possibility that all of universes fractals might collapse into one wave function that would answer all of humanities questions in a day? Could this be possible?

Answers to why we are here? What the point of life really is et al?

Is it possible that the insignificant possibility could become an escalating one that would at some point reach 100%???

Could it be at that point that the math would figure itself out so naturally that we would barely need to think about it. We would instantly understand Quantum theory and all.

Can anybody run the numbers on that probability?