3
votes
2answers
255 views

Ultrafilter-based Fourier-Walsh-like Functions

Here is a (little wild) question about Boolean functions with countably many variables and a wild analog for Fourier-Walsh functions and analysis based on them. Let $x_1,x_2,\dots,x_n,\dots$ be ...
6
votes
4answers
841 views

fourier analytic proofs

While searching through Mathoverflow, I found out a fourier analytic proof of the Isoperimetric Inequality.Also, by google search I found a fourier analytic proof of Quadratic Reciprocity theorem.I ...
6
votes
1answer
281 views

faces in the discrete cube

This arose from a question Gil Kalai asked about a problem I posed involving the Fourier transform on the discrete cube. Maybe it is more tractable. I'm afraid I'm not sure how to do this kind of ...
26
votes
0answers
1k views

Fourier transform on the discrete cube

Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$. The following is an asymptotic question. "Close to one" means "more than ...
5
votes
1answer
290 views

Kahn-Kalai-Linial for intersecting upsets

Is there any known improvement on the Kahn-Kalai-Linial inequality (on the influences of boolean functions) in the special case in which $f$ is the indicator function of an intersecting monotonic set ...
28
votes
3answers
2k views

Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

Hi. Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway... Consider this problem. I've been trying to find a formula to expand the "regular iteration" ...
15
votes
3answers
1k views

What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
10
votes
1answer
562 views

Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

Consider functions on the discrete cube $\{-1,1\}^n$. We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of ...
29
votes
1answer
2k views

Is the set of primes “translation-finite”?

The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be ...
2
votes
3answers
319 views

Multiplication of (0,1) matrices

is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?