1
$\begingroup$

Given a continuous and deriviable function of many variables, how do I know when this function is equals to zero on all the corners (or vertices) of a unit hypercube, i.e. all points, where each coordinate is equals either to 1 or 0.

I think that if I explore the function inside or/and around the unit hypercube, I will be able to tell if:

∀x1...xn: x1∈{0,1} ∧ ... ∧ xn∈{0,1} then f(x1, ... , xn)=0 where $f: \Bbb{R}^n\rightarrow\Bbb{R}$

By exploring the function, I can compute the partial derivatives of each variable and/or multiple integrals and/or gradients and/or normal vectors, etc but I don't know what exploration should I do exactly to find out the answer.

If I know how the function behaves on the half point, i.e. (0.5, ... , 0.5), which is the center of the unit hypercube, can I find the answer to my question?

Any idea?

Note: you can assume that the given function is analytic.

$\endgroup$
  • 1
    $\begingroup$ can't you just compute the function at those points? $\endgroup$ – thedude Jul 13 '17 at 22:51
  • 1
    $\begingroup$ Continuity and even smoothness is insufficient: the existence of bump functions means that for any $\epsilon > 0$, if you know your function $f$ and all of its derivatives everywhere but balls of radius $\epsilon$ around the vertices, that still provides no information about $f$ at the vertices. To be able to do something like you ask, you need your function to be analytic. $\endgroup$ – Arun Debray Jul 14 '17 at 0:01
  • 1
    $\begingroup$ Be careful that you don't have SAT as a sub-problem or else a fast solution will be too hard! $\endgroup$ – John Wiltshire-Gordon Jul 14 '17 at 0:44
  • 1
    $\begingroup$ Well, $\lnot x=1-x$, $x\wedge y=xy$ and $x\vee y=x+y-xy$, so any 3-SAT is a quickly computable polynomial. On the other hand, you said that you can quickly compute the exact integral over the cube, which, by itself, is somewhat suspicious for a general function, analytic or not. What exactly is your function class? $\endgroup$ – fedja Jul 14 '17 at 1:08
  • 1
    $\begingroup$ There are polynomials, and there are polynomials. Computing the integral of a polynomial given as a sum of monomials is easy. Computing the integral of a polynomial given as a product of a lot of factors (as you have in the 3-SAT example) is hard. $\endgroup$ – Robert Israel Jul 14 '17 at 1:25
3
$\begingroup$

Since $x^m = x$ for $x \in \{0,1\}$ and $m \ge 1$, we may assume wlog all exponents in your polynomial are $0$ or $1$. Thus your polynomial can be written as $$P(x) = \sum_{\alpha \in A} c_\alpha x^\alpha$$ where $A$ is a collection of not too many subsets of $\{1,\ldots, n\}$ and $x^\alpha = \prod_{j \in \alpha} x^j$. Thus $P$ is $0$ at every point of the hypercube iff $P(\chi_\beta) = \sum_{\alpha \in A: \alpha \subseteq \beta} c_\alpha = 0$ for every subset $\beta$ of $\{1,\ldots,n\}$. Of course we remove all terms where $c_\alpha = 0$. Now unless $A$ is empty, there must be some $\alpha \in A$ that is minimal (i.e. has no proper subset in $A$). If so, $P(\chi_\alpha) = c_\alpha \ne 0$. So the only case where $P(x)$ is $0$ at all corners of the hypercube is where $A$ is empty, i.e. the polynomial is identically $0$.

$\endgroup$
  • $\begingroup$ And if I want to tell whether function f is equals to 1, not 0, at all the corners/vertices of the hypercube? How much the existing method should be changed for that? $\endgroup$ – Farewell Stack Exchange Jul 14 '17 at 2:57
  • $\begingroup$ It would have to be identically $1$. $\endgroup$ – Robert Israel Jul 14 '17 at 5:04
  • $\begingroup$ identically 0 means that function f defined to be f(x1, ... , xn) = 0 and identically 1 means that function f defined to be f(x1, ... , xn) = 1 ? $\endgroup$ – Farewell Stack Exchange Jul 14 '17 at 11:03
  • $\begingroup$ Yes (for the function written in the form I gave). $\endgroup$ – Robert Israel Jul 14 '17 at 16:18
  • $\begingroup$ Okay, understood. Thanks for the answer. $\endgroup$ – Farewell Stack Exchange Jul 14 '17 at 16:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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