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$
19
  • 1
    $\begingroup$ can't you just compute the function at those points? $\endgroup$
    – thedude
    Jul 13, 2017 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$ Jul 14, 2017 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$ Jul 14, 2017 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, 2017 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$ Jul 14, 2017 at 1:25

1 Answer 1

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$
5
  • $\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$ Jul 14, 2017 at 2:57
  • $\begingroup$ It would have to be identically $1$. $\endgroup$ Jul 14, 2017 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$ Jul 14, 2017 at 11:03
  • $\begingroup$ Yes (for the function written in the form I gave). $\endgroup$ Jul 14, 2017 at 16:18
  • $\begingroup$ Okay, understood. Thanks for the answer. $\endgroup$ Jul 14, 2017 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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