Skip to main content
3 of 4
edited body
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

Here is a family with cardinality continuum. For a nonnegative integer $n$, let the base $2$ expansion of $n$ be $$n = \sum_{k=0}^{\infty} b_k(n) 2^k.$$ So $b_k(n) \in \{ 0, 1 \}$ and is equal to $0$ for all but finitely many $k$.

Now, let $\lambda = (\lambda_0, \lambda_1, \ldots, )$ be any sequence in $\{ 0, 1 \}^{\infty}$ and define $$\chi_{\lambda}(n) = (-1)^{\sum_k b_k(n) \lambda_k}.$$

I claim that $\chi_{\lambda}$ and $\chi_{\mu}$ are almost orthogonal for all $\lambda \neq \mu$.

Let $k$ be an index for which $\lambda_k \neq \mu_k$. For $n = 2^{k+1} m + r$ with $0 \leq r < 2^{k+1}$, we have $\chi_{\lambda}(n) = \chi_{\lambda}(2^{k+1} m) \chi_{\lambda}(r)$. Therefore, $$\sum_{n=2^{k+1} m}^{2^{k+1} m+2^{k+1}-1} \chi_{\lambda}(n) \chi_{\mu}(n) = \chi_{\lambda}(2^{k+1} m) \chi_{\mu}(2^{k+1} m) \sum_{r=0}^{2^{k+1}-1} \chi_{\lambda}(r) \chi_{\mu}(r)$$ $$= \chi_{\lambda}(2^{k+1} m) \chi_{\mu}(2^{k+1} m) \prod_{j=0}^{k} (1+(-1)^{\lambda_j \mu_j}) = 0.$$ The last equality is because at least one term in the product is $0$, namely $1+(-1)^{\lambda_k \mu_k}$.

So the sum of $\chi_{\lambda} \chi_{\mu}$ is $0$ over intervals of the form $[2^{k+1} m, 2^{k+1} m + 2^{k+1}-1]$, and thus the sum of $\chi_{\lambda} \chi_{\mu}$ over any $[0, N]$ is at most $2^{k+1}-1$. $\square$.

David E Speyer
  • 156.2k
  • 14
  • 419
  • 763