What is the size of these discrete function sets?












2












$begingroup$


I'm interested in the set $F_n$ of functions $f:{-1,1}^nto{-1,1}$ which can be represented as $xmapstotext{sign}(acdot x)$ for some $ainmathbf{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}^nsetminus(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 $acdot 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






linear-algebra discrete-mathematics







share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    I'm interested in the set $F_n$ of functions $f:{-1,1}^nto{-1,1}$ which can be represented as $xmapstotext{sign}(acdot x)$ for some $ainmathbf{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}^nsetminus(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 $acdot 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






    linear-algebra discrete-mathematics







    share|cite|improve this question











    $endgroup$















      2












      2








      2





      $begingroup$


      I'm interested in the set $F_n$ of functions $f:{-1,1}^nto{-1,1}$ which can be represented as $xmapstotext{sign}(acdot x)$ for some $ainmathbf{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}^nsetminus(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 $acdot 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






      linear-algebra discrete-mathematics







      share|cite|improve this question











      $endgroup$




      I'm interested in the set $F_n$ of functions $f:{-1,1}^nto{-1,1}$ which can be represented as $xmapstotext{sign}(acdot x)$ for some $ainmathbf{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}^nsetminus(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 $acdot 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






      linear-algebra discrete-mathematics




      linear-algebra discrete-mathematics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 3 '18 at 16:06







      fweth

















      asked Dec 2 '18 at 1:00









      fwethfweth

      1,148711




      1,148711






















          1 Answer
          1






          active

          oldest

          votes


















          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.






          share|cite|improve this answer











          $endgroup$









          • 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





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3022086%2fwhat-is-the-size-of-these-discrete-function-sets%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          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.






          share|cite|improve this answer











          $endgroup$









          • 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
















          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.






          share|cite|improve this answer











          $endgroup$









          • 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














          2












          2








          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.






          share|cite|improve this answer











          $endgroup$



          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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 2 '18 at 4:35

























          answered Dec 2 '18 at 2:58









          FranklinBashFranklinBash

          1012




          1012








          • 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














          • 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








          1




          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




          $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




          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




          $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




          1




          $begingroup$
          Don't worry, I'm glad you shared your intuition :)
          $endgroup$
          – fweth
          Dec 2 '18 at 4:17




          $begingroup$
          Don't worry, I'm glad you shared your intuition :)
          $endgroup$
          – fweth
          Dec 2 '18 at 4:17




          2




          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




          $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


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid …



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3022086%2fwhat-is-the-size-of-these-discrete-function-sets%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          -

          Popular posts from this blog

          Probability when a professor distributes a quiz and homework assignment to a class of n students.

          Image
          0 0 $begingroup$ Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments back to the class in a random fashion for grading. Each student receives one quiz and one homework assignment to grade. (a) What is the probability that every student receives someone else's quiz to grade, and someone else's homework to grade? (b) What is the probability that no student receives both their own quiz and their own homework assignment to grade? In this case, some students may receive their own quiz, and others may receive their own homework assignment. (c) Compute the limiting probability as n approaches infinity in each case. ...
          Read more

          Aardman Animations

          Image
          Aardman Animations, Ltd. Aardman Animations Tipo privada Atividade Animação em stop-motion , Animação em CGI Fundação 1972 Fundador(es) Peter Lord David Sproxton Sede Bristol, Inglaterra  Reino Unido Proprietário(s) Dreamworks Pessoas-chave Peter Lord David Sproxton Nick Park Divisões Aardman Features Aardman Digital Aardman Commercials Aardman Broadcast Aardman International Aardman Rights Aardman Effects Aardman 3-D Systems Aardman Nathan Love AardBoiled Website oficial aardman.com ...
          Read more

          Are they similar matrix

          Image
          0 $begingroup$ Do $begin{bmatrix} 0&i&0\0&0&1\0&0&0 end{bmatrix} $ and $begin{bmatrix} 0&0&0\-i&0&0\0&1&0 end{bmatrix} $ are similar.Is this True/false Clearly both are nilpotent and one is conjucate transpose of other but how to know if they are similar.i'm stuck. Please help me linear-algebra vector-spaces eigenvalues-eigenvectors generalizedeigenvector share | cite | improve this question edited Dec 10 '18 at 6:38 Vasanth Kris asked Dec 10 '18 at 6:19 ...
          Read more