Shattering with sinusoids

131 Views Asked by At

Let $d \geq 2$ and $K$ some positive integer. Consider distinct points $\theta_1, \ldots, \theta_K\in \mathbb{T}^d$ and (not necessarily distinct) $z_1, \ldots, z_K \in \{-1,1\}$, does there exist an eigenfunction of the Laplacian $f: \mathbb{T}^d \to \mathbb{R}$ such that $sgn(f(\theta_i)) = z_i$ for all $i$?

Here sgn is signum function.

Inspired by this question

1

There are 1 best solutions below

0
On

I'll use $\mathbb T=\mathbb Z/2\pi\mathbb Z.$

For generic choices of $\theta_1,\dots,\theta_K$ there is an $n$ such that $\operatorname{sgn}(\sin(n(\theta_i)_1))=z_i$ for $i=1,\dots,K.$ If we have the following irrationality condition in the first co-ordinate:

$$k_1(\theta_1)_1+\cdots+k_K(\theta_K)_1\neq 0\in\mathbb T^d\text{ for all non-zero }k\in\mathbb Z^d$$

then the sequence $(n(\theta_1)_1,\dots,n(\theta_K)_1)$ is dense in $\mathbb T^K$ - see for example Exercise 5 here for a much stronger quantitative result. The set of $t\in\mathbb T^K$ such that $\operatorname{sgn}(\sin(t_i))=z_i$ for $i=1,\dots, K$ is an non-empty open set, so any dense set will intersect it.

On the other hand, for any $d$ there are counterexamples for special values of $K,\theta_1,\dots,\theta_K.$ The argument is basically by counting dimensions. Take $p$ to be a prime with

$$2^{d+3}<p< e^{p^d/8}.$$

Take $K=p^d$ and take $\theta_1,\dots,\theta_K$ to be an enumeration of $\{0,2\pi\tfrac1p,\dots,2\pi\tfrac{p-1}p\}^d=\{x\in\mathbb T^d\mid px=0\}.$

Every eigenfunction on $\mathbb T^d,$ when restricted to $\{x\mid px=0\},$ can be written in the form $f_{\lambda,A}(x)=\mathrm{Re}\sum A_k e^{k\cdot x},$ where $\lambda\in\mathbb Z/p\mathbb Z,$ and the sum is over $k\in(\mathbb Z/p\mathbb Z)^d$ satisfying $k_1^2+\dots+k_d^2=\lambda\pmod{p},$ and $A_k\in\mathbb C.$

There are $p$ different values of $\lambda.$ For each $\lambda$ there are at most $2^dp^{d-1}$ solutions of $k_1^2+\dots+k_d^2=\lambda\pmod{p}$ - at most $p^{d-1}$ choices of $k_1^2,\dots,k_d^2,$ then $2^d$ choices of square roots $k_1,\dots,k_d.$ This gives at most $2^{d+1}p^{d-1}\leq p^d/4$ real dimensions. Linear classifiers with $m$ real dimensions have VC dimension $m,$ so by Sauer-Shelah, functions of the form $f_{\lambda,A}$ (for fixed $\lambda$) can achieve at most

$$\sum_{i=0}^{\lfloor p^d/4\rfloor}\binom{p^d}{i}$$

vectors $(\operatorname{sgn}(f_{\lambda,A}(\theta_1),\dots,\operatorname{sgn}(f_{\lambda,A}(\theta_{p^d})))\in\{-1,1\}^{p^d}.$ By Hoeffding's inequality this is at most $e^{-p^d/8}2^{p^d}.$ By a union bound over the $p$ choices of $\lambda,$ there are at most $pe^{-p^d/8}2^{p^d}<2^{p^d}$ vectors achieved by any $f_{\lambda,A}.$ So there is some combination of signs that is not achieved by any eigenfunction.