20
$\begingroup$

Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\in\omega$ such that for all $n\in\omega$ we have $$\Big|\sum_{k=0}^n\big(f(k)\cdot g(k)\big)\Big|<C_0.$$

Suppose that ${\cal D}\subseteq \{-1,1\}^\omega$ has the property that whenever $f\neq g \in {\cal D}$, then $f,g$ are almost orthogonal.

Question. What possible cardinalities can ${\cal D}$ have?

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ You can certainly have an infinite family of mutually almost orthogonal functions: for every $n$, let $f_n$ be the sequence of $n$ $1$s, followed by $n$ $-1$s, then $n$ $1$s, then $n$ $-1$s, etc. But can there be an uncountable family? . . . $\endgroup$
    – Will Brian
    Commented Aug 30 at 10:06
  • 3
    $\begingroup$ I suspect that the functions $(-1)^{\lfloor \alpha n \rfloor}$ work, where $\alpha$ ranges over some $S \subset \mathbb{R}$ such that $\alpha/\beta$ is irrational for all distinct $\alpha$, $\beta \in S$. (If we allowed functions valued in $[-1,1]$ instead of $\{ -1, 1 \}$, then $\{ \cos (\alpha n): \alpha \in S \}$ does work.) But I couldn't prove the bound. $\endgroup$
    – David E Speyer
    Commented Aug 30 at 12:50
  • 2
    $\begingroup$ @DavidESpeyer I guess this is a bit too strong, probably some Diophantine approximability has to enter the picture. For example, if $\alpha=2$ and $\beta = \sum_k 1/ a_k!$ for a fast growing sequence $a_k$, then $(-1)^{\lfloor \alpha n \rfloor + \lfloor \beta n \rfloor}$ is constant on very large intervals starting at $a_k$, so the bound cannot hold. $\endgroup$
    – Mikael de la Salle
    Commented Aug 30 at 13:32
  • 2
    $\begingroup$ Humm, my comment got upvotes so I guess somebody found something meaningful there... but I have to admit that I do no longer understand what I meant. $\endgroup$
    – Mikael de la Salle
    Commented Aug 30 at 15:28
  • 2
    $\begingroup$ Is it true that for every countable set $C\subseteq \{-1,1\}^\omega$ there exists a function $f\in\{-1,1\}^\omega$, almost orthgonal to every function in the set $C$? $\endgroup$
    – Taras Banakh
    Commented Aug 30 at 17:54

1 Answer 1

Reset to default
18
$\begingroup$

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$. Thus $\lambda_k + \mu_k = 1$. 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$.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ @DavidESpeyer Maybe $b_k(n)$ is equal to $0$ (not to $1$) for all but finitely many $k$? $\endgroup$
    – Taras Banakh
    Commented Aug 30 at 17:50
  • 3
    $\begingroup$ @TarasBanakh Oops! That's the trouble with thinking multiplicatively and writing additively. Fixed now. $\endgroup$
    – David E Speyer
    Commented Aug 30 at 18:01
  • 4
    $\begingroup$ Might I suggest including the proof of $$\prod_{j=0}^{k} (1+(-1)^{\lambda_j \mu_j}) = \sum_{r=0}^{2^{k+1}-1} \chi_{\lambda}(r) \chi_{\mu}(r)$$. It is a lot of mental steps! $\endgroup$
    – Christopher King
    Commented Aug 30 at 18:17
  • 2
    $\begingroup$ Might I suggest $$\begin{align}\prod_{j=0}^{k} \left((-1)^{0(\lambda_j+\mu_j)}+(-1)^{1(\lambda_j+\mu_j})\right) = \sum_{(b_j)\in\{0,1\}^{k+1}}\prod_{j=0}^{k} (-1)^{b_j(\lambda_j+\mu_j)}\\ = \sum_{(b_j)\in\{0,1\}^{k+1}}(-1)^{\sum_{j=0}^{k}b_j(\lambda_j+\mu_j)}\\ = \sum_{r=0}^{2^{k+1}-1}(-1)^{\sum_{j=0}^{k}b_j(r)\lambda_j}(-1)^{\sum_{j=0}^{k}b_j(r)\mu_j}\;?\end{align}$$ $\endgroup$
    – Claude Chaunier
    Commented Aug 31 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .