# Given a continuous function of many variables, how do I know when this function is equals to zero on all the corners of a unit hypercube?

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.

• can't you just compute the function at those points? – thedude Jul 13 '17 at 22:51
• 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. – Arun Debray Jul 14 '17 at 0:01
• Be careful that you don't have SAT as a sub-problem or else a fast solution will be too hard! – John Wiltshire-Gordon Jul 14 '17 at 0:44
• 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? – fedja Jul 14 '17 at 1:08
• 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. – Robert Israel Jul 14 '17 at 1:25

## 1 Answer

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$.

• 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? – Farewell Stack Exchange Jul 14 '17 at 2:57
• It would have to be identically $1$. – Robert Israel Jul 14 '17 at 5:04
• 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 ? – Farewell Stack Exchange Jul 14 '17 at 11:03
• Yes (for the function written in the form I gave). – Robert Israel Jul 14 '17 at 16:18
• Okay, understood. Thanks for the answer. – Farewell Stack Exchange Jul 14 '17 at 16:31