# Tagged Questions

**5**

votes

**5**answers

253 views

### Characterizing and counting boolean functions with all influences 1/2

Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$,
so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there ...

**3**

votes

**2**answers

338 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

**4**answers

858 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

**1**answer

299 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 ...

**30**

votes

**0**answers

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

**1**answer

310 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

**3**answers

3k 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

**3**answers

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

**1**answer

601 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

**1**answer

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

**3**answers

319 views

### Multiplication of (0,1) matrices

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