2
$\begingroup$

I'm interested in the set $F_n$ of functions $f:\{-1,1\}^n\to\{-1,1\}$ which can be represented as $x\mapsto\text{sign}(a\cdot x)$ for some $a\in\mathbf{R}^n$. What is the size of $F_n$? Is there some discrete encoding which is 'better' then to write down the complete lookup table?

My idea is to look at the number of connected components in $\mathbf{R}^n\setminus(\cup_x\{x\}^\bot)$, since if $a,a'$ represent different functions $f,f'$, say $f(y)\neq f'(y)$, then I can't go from $a$ to $a'$ without crossing the border $a\cdot y=0$. But I still don't know how many such components there are.

[EDIT] I just tried to plot the planes $\{x\}^\bot$ in $\mathbf{R}^3$ (w.l.o.g. $x_1=1$ since $\{x\}^\bot=\{-x\}^\bot$), there seem to be $14$ partitions and they seem to correspond to the faces and edges of the $[-1,1]^3$-cube. But in even dimensions the picture needs to be different since the edges of the $[-1,1]^{2n}$-cube lie directly on the planes

$\endgroup$
2
$\begingroup$

EDIT: My previous rough idea about orthants was completely off of the mark. I need to go rethink everything.

I have provided a link to a set of slides in the comments below, but I think I'm starting to get out of my depth. Someone who knows better than I should swoop in and save the day.

$\endgroup$
4
  • 1
    $\begingroup$ Hey, thanks a lot for the input! I just tried to plot the planes $\{x\}^\bot$ in $\mathbf{R}^3$ (w.l.o.g. $x_1=1$ since $\{x\}^\bot=\{-x\}^\bot$), but the resulting components don't look like orthants to me, some of them are enclosed by four planes but some only by three. Or am I confused about this? $\endgroup$ – fweth Dec 2 '18 at 3:25
  • 1
    $\begingroup$ @fweth Oh man, what I wrote was truly a half baked idea if there ever was one. My very first line is obviously false; these are not spokes of a coordinate system as there are WAY too many of them, even after accounting for negatives. Sorry, back to the drawing board for me... $\endgroup$ – FranklinBash Dec 2 '18 at 3:36
  • 1
    $\begingroup$ Don't worry, I'm glad you shared your intuition :) $\endgroup$ – fweth Dec 2 '18 at 4:17
  • 2
    $\begingroup$ @fweth I found an interesting set of slides about counting regions of $\mathbb{R}^n$ that have been separated by hyperplanes. They even discuss what to do with hyperplanes that are not in general position, which is what we have here. It also looks a bit complicated. physics.csusb.edu/%7Eprenteln/papers/hyperintro.pdf $\endgroup$ – FranklinBash Dec 2 '18 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.