Timeline for What is the degree of a symmetric boolean function?
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 3, 2011 at 8:03 | vote | accept | Shir | ||
| Sep 2, 2011 at 5:11 | vote | accept | Shir | ||
| Sep 2, 2011 at 5:18 | |||||
| Sep 1, 2011 at 19:43 | history | edited | Shir | CC BY-SA 3.0 |
Added the open problem tag, changed title to reflect true nature of question
|
| Sep 1, 2011 at 18:16 | answer | added | Gjergji Zaimi | timeline score: 6 | |
| Sep 1, 2011 at 17:15 | comment | added | Gerhard Paseman | I would not delete the question. You can edit it and flag for moderator attention. I recommend an open-problem tag and words in the question itself to reflect that. Gerhard "Ask Me About System Design" Paseman, 2011.09.01 | |
| Sep 1, 2011 at 11:06 | comment | added | Shir | Update: This is actually equivalent to a question I was trying to solve (about the n-th Fourier coefficient of symmetric boolean functions), that I just found is open, so I withdraw the question, as I understand this is not in accordance with MO guidelines. | |
| Sep 1, 2011 at 11:06 | history | edited | Shir | CC BY-SA 3.0 |
deleted 247 characters in body
|
| Sep 1, 2011 at 10:46 | history | edited | Shir | CC BY-SA 3.0 |
added 255 characters in body
|
| Sep 1, 2011 at 10:01 | comment | added | Shir | P.S. - I'm not allowed to add new tags, and there's no 'additive-number-theory' tag. | |
| Sep 1, 2011 at 10:01 | comment | added | Shir | A friend ran a computer simulation and found that for 16 and 18, for instance, we have no other option but to sum the coefficients with alternating signs (i.e. $(-1)^j$), that's what inspired the use of N, since it follows that even if there is such a sequence, then it must be that N>18. (this is in part what leads me to believe that there is no such sequence) | |
| Sep 1, 2011 at 8:00 | comment | added | darij grinberg | On the $14$-th line of the Pascal triangle, we have $1-14+91-364-1001+2002-3003-3432+3003+2002+1001-364+91-14+1=0$. This leads to a nonconstant $p_{14}$. I am not sure whether this is a sporadic or a recurring phenomenon. Anyway I propose tagging the question "additive-number-theory". | |
| Sep 1, 2011 at 7:45 | comment | added | Shir | Darij, yes, this is exactly what I'm asking. | |
| Sep 1, 2011 at 2:01 | comment | added | Gerhard Paseman | Let's take n=8. Mod 7 the row is 1 1. 0 0 0 0 0 1 1, which says something about the end members of p_8. But also nod 5, the row is 1 3 3 1 0 1 3 3 1, which implies additional constraints mod 5. In general there will be for n=2k pi(2k) - pi(k) such constraints, which might be enough to pin p_2k down to a constant. Gerhard "Ask Me About System Design" Paseman, 2011.08.31 | |
| Aug 31, 2011 at 22:45 | comment | added | darij grinberg | I don't really get it. Are you simply asking for which $n\geq 0$ we can partition the $n$-th row of the Pascal triangle (seen as a multiset) in two submultisets with equal sum, other than by putting the elements alternately in each of the two parts? | |
| Aug 31, 2011 at 22:09 | comment | added | Shir | Gerhard, would you mind going into details? I don't quite follow. | |
| Aug 31, 2011 at 22:08 | comment | added | Shir | Yes Pietro, it concerns only even $n$, but I thought that a more detailed presentation would cloud the essence of the question. | |
| Aug 31, 2011 at 20:07 | comment | added | Gerhard Paseman | To make up for my earlier gaffe, notice that for p a prime, the pth, p+1st, and later rows have very few entries which are not 0 mod p. (Indeed, mod p they look like 2 new copies of Pascal's triangle.) This along with the frequency of primes suggests to me that you will not be able to get all the functions non constant. Gerhard "Ask Me About System Design" Paseman, 2011.08.31 | |
| Aug 31, 2011 at 20:05 | comment | added | Pietro Majer | (with - instead of + I guess) | |
| Aug 31, 2011 at 20:00 | comment | added | Pietro Majer | For odd n the relation is satisfied if $p_n(i)+p_n(n-i)=0$ for all $i$. In this case, there are at least $\frac{n+1}{2}$ choices for pn. So your question concerns even $n$ only, right? | |
| Aug 31, 2011 at 19:58 | comment | added | Gerhard Paseman | I just noticed the big N. Never miNd. Gerhard "Time To Get Different Glasses" Paseman, 2011.08.31 | |
| Aug 31, 2011 at 19:33 | comment | added | Gerhard Paseman | What would you suggest for p_1 and p_2? Gerhard "They Look Constant To Me" Paseman, 2011.08.31 | |
| Aug 31, 2011 at 19:09 | history | asked | Shir | CC BY-SA 3.0 |