Indistinguishable sceneries on the Boolean hypercube
Renan Gross Uri Grupel

	
	
	
		Indistinguishable sceneries on the Boolean hypercube
    Renan Gross[Weizmann Institute of Science. renan.gross@weizmann.ac.il]
		 and Uri Grupel[Weizmann Institute of Science. uri.grupel@weizmann.ac.il. Supported by the European Research Council (ERC).]
    
=========================================================================================================================================================================================================


	
	
		We show that the scenery reconstruction problem on the Boolean hypercube is in general impossible. This is done by using locally biased functions, in which every vertex has a constant fraction of neighbors colored by 1, and locally stable functions, in which every vertex has a constant fraction of neighbors colored by its own color. Our methods are constructive, and also give super-polynomial lower bounds on the number of locally biased and locally stable functions. We further show similar results for ^n and other graphs, and offer several follow-up questions.
	
	
	
	
	
	

§ INTRODUCTION

	Let f : -1,1^n→-1,1 be a Boolean function on the n-dimensional hypercube, and let S_i be a random walk on the hypercube. Can we reconstruct the function f (with probability 1, up to the hypercube's symmetries) by only observing the scenery process f(S_i)_i?
	
	Similar questions have been raised for other graphs. For example, it was shown in <cit.> that when G is a cycle graph, the answer is yes: it is possible to reconstruct the function f (which is a string up to choice of origin) up to rotation and reflection with probability 1. It is still an open question whether any such string can be reconstructed in polynomial time. When G=, reconstruction is generally impossible <cit.>; for random sceneries on  see <cit.>.
	
	When G is the hypercube, such a process was studied for a specific Boolean function, the percolation crossing, under the notion of dynamical percolation; see <cit.> for details. 
	
	In the general case, however, we show that for n≥ 4 the answer is no. We do this by considering a pair of non-isomorphic functions f and g such that if S_i and T_i are random walks on the hypercube, then f(S_i) and g(T_i) have exactly the same distribution. We discuss two different classes of such functions:
	
	
		
  * Locally p-biased functions: Let G be a graph. A Boolean function f: G →-1,1 is called locally p-biased, if for every vertex x∈ G we have
		
    {y∼ x; f(y) = 1}/deg(x)=p.

		In words, f is locally p-biased if for every vertex x, f takes the value 1 on exactly a p-fraction of x's neighbors. If f is a locally p-biased function, then the random variables {f(S_i)}_i have the same distribution as independent Bernoulli random variables with (f(S_i)=1)=p. 
			
		
  * Locally p-stable functions: Let G be a graph. A Boolean function f: G →-1,1 is called locally p-stable, if for every vertex x∈ G we have
		
    {y∼ x; f(x) = f(y)}/deg(x)=p.

		In words, f is locally p-stable if for every vertex x, f retains its value on exactly a p-fraction of x's neighbors. If f is locally p-stable, then the random variables {f(S_i)f(S_i+1)}_i have the same distribution as independent Bernoulli random variables with (f(S_i)f(S_i+1)=1)=p.
	
	
	We say that two Boolean functions f,g:{-1,1}^n→{-1,1} are isomorphic, if there exists an automorphism of the hypercube ψ:{-1,1}^n→{-1,1}^n such that f∘ψ = g. Two functions are non-isomorphic if no such ψ exists.
		
	The existence of two non-isomorphic locally p-biased functions, or two non-isomorphic locally p-stable functions thus render scenery reconstruction on the hypercube impossible. 
	
	It is not immediately obvious that pairs of non-isomorphic locally p-biased and pairs of non-isomorphic locally p-stable functions exist. It is then natural to ask, for which p values do they exist? If they do exist, how many of them are there?
		
	In this paper, we characterize the possible p values on the n-dimensional hypercube, give bounds on the number of non-isomorphic pairs, and discuss results on other graphs. The paper is organized as follows.
	
	In  <ref> we give a full characterization of the connection between the dimension of the hypercube n and the permissible p values of locally p-biased functions, as expressed in the following theorem:
	
	
		Let n ∈ be a natural number and p ∈ [0,1]. There exists a locally p-biased function f:-1,1^n→-1,1 if and only if p = b/2^k for some integers b ≥ 0, k ≥ 0, and 2^k divides n. 
		
	
	Our proof can construct functions for all p of the above form.
	
	In  <ref> we inspect the class size of non-isomorphic locally p-biased functions on the hypercube. We show that the class size for p=1/2 is at least C2^√(n)/n^1/4 for some constant C > 0, and for p=1/n is super-exponential in n, when such p values are permissible. Thus reconstruction is impossible for such functions. We conjecture that the number of non-isomorphic locally p-biased functions scales quickly for all permissible p values:
	
		Let n>0 be even. Let p=b/2^k, where 1≤ b≤ 2^k, k≥ 1 and 2^k divides n. Let B_p^n be the set of non-isomorphic locally p-biased functions. Then B_p^n is super-exponential in n.
		
	
	In  <ref> we briefly discuss locally p-stable functions. We show that they exist for all possible p values, and that for most p values there are many non-isomorphic pairs; however, for every n, there are p values for which there is a single unique locally p-stable function. The results in this section are based on those of  <ref>.
	
	In  <ref> we discuss other graphs. First, we show that when G is a regular tree of degree n, then all p=a/n are permissible. Second, we show that for G=^n all the results for the hypercubes hold true. This gives us a partial answer for permissible p values for ^n, but there are additional values that cannot be achieved through the hypercube construction: for example, for n=1 we can define a function with p=1/2 and when n=2 we can find a function with p=1/4. We also discuss other Cayley graphs of , and suggest further questions on scenerey reconstruction.
	
	Throughout most of this paper we treat the Boolean hypercube as the set -1,1^n. We identify it with the 0,1^n hypercube by considering -1 in the first to correspond to 0 in the second.		
	
	
	
	

§ CHARACTERIZATION OF PERMISSIBLE P VALUES

	In this section we prove Theorem <ref>. The “only if” part is achieved by a double counting argument.
	
		Suppose that f:-1,1^n→-1,1 is a locally p-biased Boolean function. Let x be a uniformly random element of -1,1^n. Then f(x) is f's value on a uniformly random point of the hypercube, and is equal to 1 with probability l/2^n, where l = x ∈-1,1^n ;  f(x) = 1 is the number of vertices on which f obtains the value 1. Now let y be a uniformly random neighbor of x. The function f is locally p-biased, so probability that f(y) = 1 is p by definition. Since both x and y are uniform random vertices, (f(x) = 1) = (f(y) = 1). Denoting p = m/n for some m ∈0,1,…,n, this gives
		
    p = l/2^n = m/n.

		Decompose n into its prime powers, writing n = c2^k, where c is odd. Then by (<ref>), we have that
		
		
    l = 2^n-k· m/c

		is an integer, and so c must divide m, i.e m = bc for some b. But then
		
		
    p = m/n = b/2^k

		as stated by the theorem.
	
	
	The “if” part of Theorem <ref> is given by an explicit construction, performed in three steps. First, we use perfect codes in order to obtain a locally 1/n-biased function for n that is a power of two. Second, we extend the result to a locally m/n-biased function by taking the union of m locally 1/n-biased functions with disjoint support. Finally, given a locally p-biased function on n bits, we show how to manipulate its Fourier representation in order to yield a locally p-biased function on cn bits for any c.

	We begin with a brief review of binary codes. We omit proofs and simply state definitions and known results; for a more thorough introduction, see e.g <cit.>.
	
	A binary code C on the n-dimensional hypercube is simply a subset of -1,1^n; its elements are called codewords. The distance of a code C is defined as min_x,y ∈ Cδ_H(x,y), where δ_H(x,y)  = i ∈1,…,n; x_i ≠ y_i is the Hamming distance between x and y, that is, the number of coordinates in which x and y differ. A code of odd distance d is called perfect if the Hamming balls of radius (d-1)/2 around each codeword completely tile the hypercube without overlaps. A code is called linear if its codewords form a vector space over _2.
	
	A particularly interesting code is the Hamming code with k data bits, denoted H_k. It is a linear, distance-3 perfect code on the hypercube of dimension n = 2^k -1. Its codewords are structured as follows. For x ∈ H_k and i ∈1,…,n, the bit x_i is called a parity bit if i is a power of 2, and data bit otherwise. Thus every codeword contains k parity bits and 2^k - k -1 data bits. The data bits range over all 
	possible bit-strings on 2^k -k -1 bits, while the parity bits are a function of the data bits: 	
	
    x_i = ⊕_j: i  j ≠ 0 x_j     ∀ i = 2^l, l≥0
 
	where ⊕ denotes exclusive bitwise or (xor), and  denotes bitwise AND. In words, the parity bit x_i is equal to the xor of all data bits x_j such that the bitwise AND between i and j is non-zero. Thus there are 2^k - k - 1 codewords in H_k. 
		
	Armed with perfect codes, we are ready to start our proof.
	
	
		Let n = 2^k be a power of two. Then there exists a locally 1/n-biased function on -1,1^n.
	
	
	
		In a locally 1/n-biased function f, every point in the hypercube must have exactly 1 neighbor which is given the value 1, and n-1 neighbors which are given the value -1.
		
		Let C be a distance-3 perfect code on the n-1 = 2^k - 1-dimensional hypercube. That is, every two code words in C are at a Hamming distance of at least 3 from each other, and the Hamming balls of radius 1 centered around each codeword completely tile the hypercube. Such codes exist for dimension 2^k-1; for example, as mentioned above and shown in <cit.>, the Hamming code is such a code. Define f:-1,1^n →-1,1 to be the following function:
		
		
    f(x) = 
    		1,     x∈ C×{-1,1}
    
    		-1,    otherwise.

		In words, f(x) takes the value of 1 whenever the first n-1 coordinates of x are a codeword in C, and otherwise takes the value of -1. Then f is a locally 1/n-biased function:
		-
			
  * If f(x) = 1, then x=(y,b)∈ C×{-1,1}. Thus x' = (y,-b) is the only neighbor of x on which f(x') = 1; any other neighbor differs from x in the first n-1 coordinates, and since C is a distance-3 code, these coordinates are not a codeword in C.
			
  * If  f(x) = -1, then x=(y,b) where b∈{-1,1} and y is not a codeword of C.
			Since C is perfect, y must fall inside some radius-1 ball of a codeword z. Then x' = (z,b) is the only neighbor of x such that f(x') = 1; any other codeword differs from z in at least 3 coordinates since C is a distance-3 code, and so differs from y in at least 2.
		
	
	
	
		Let n = 2^k be a power of two. Then there exists a locally m/n-biased function on -1,1^n for any m = 0, 1, …, n.
	
	
	
		For m = 0 the statement is trivial. Let m ∈1,…,n. In order to construct a locally m/n-biased function, it is enough to find m locally 1/n-biased functions f_1, …, f_m with pairwise disjoint support, i.e x : f_i(x) = 1∩x : f_j(x) = 1 = ∅ for all i ≠ j. With these functions, we can define f in the following manner:
		
		
    f(x) = 
    		1,     f_i(x) = 1  for some i
    
    		-1,    otherwise.

		Then f is a locally m/n-biased function: For every x ∈1,-1^n, consider its neighbors on which f takes the value 1, i.e the set y ;  d(x,y) = 1, ∃ i  s.t  f_i(y) = 1. Each f_i contributes exactly one element to this set, since it is a locally	1/n-biased function; further, these elements are all distinct, since the f_i's have pairwise disjoint supports. So x has m neighbors on which f takes the value 1.
		
		Recall that the Hamming code on 2^k-1 bits uses 2^k-k-1 data bits (these range over all possible bit-strings on 2^k-k-1 bits) and k parity bits (these are a function of the data bits). Let C be the Hamming code on 2^k-1 bits, and rearrange the order of the bits so that the parity bits are all on the right hand side of the codeword, i.e each codeword x can be written as x = (y,z) where y is a word of length 2^k-k-1 constituting the data bits and z is a word of length k constituting the parity bits.
		
		Now, for all 1 ≤ i ≤ n, define the sets C_i = x ⊕ (i-1) ;  x ∈ C, where ⊕ denotes the exclusive or (xor) operator. Then the sets C_i are all pairwise disjoint: in order for two words x = (y,z) ∈ C_i and x' = (y',z') ∈ C_j to be the same,  we need to have both y = y' and z = z'. But if y = y' then the data bits are the same, and by construction z ⊕ z' = (i-1) ⊕ (j-1), so z ≠ z' if i ≠ j. Further, since xoring by a constant only amounts to a rotation of the hypercube, each C_i is still a perfect code.
		
		Let f_i be the function which uses C_i as its perfect code in the proof of Lemma <ref>. Then, f_1, …, f_n are n locally 1/n-biased functions  with pairwise disjoint supports. The combination of any m of these functions yields a locally m/n-biased function.
		
	
	
	
	
		Let f:-1,1^n→-1,1 be a locally p-biased function on the n-dimensional hypercube.
		Let c ∈, and define a new function f':-1,1^cn→-1,1 by
		
    f'(x)     =      f(∏_j=0^c-1x_1+jn,…,∏_j=0^c-1x_n+jn).

		Then f' is a locally p-biased function. 
		
	
	
	
		Let x' ∈-1,1^cn be a point on the cn-dimensional hypercube, and let y ∈-1,1^n be such that y_i = x'_i·…· x'_(c-1)n+i. Then by definition, f'(x') = f(y). Since f is a locally p-biased function, y has pn neighbors on which f takes the value 1. Each of these neighbors is obtained from y by flipping a single coordinate y_i; this amounts to changing any one of the c coordinates of x' which make up the y_i. Since the y_i's are disjoint monomials in the coordinates of x', this implies that there are at least pcn neighbors of x' on which f' takes the value 1. 
		
		The same argument can be repeated for the value -1 instead of 1, showing that there are at least (1-p)cn neighbors of x' on which f' takes the value -1. But since the number of neighbors of x' is nc, the inequalities are in fact equalities. Hence, there are exactly pcn neighbors of x' on which f' takes the value 1, completing the proof.
	
	
	We are now ready to prove that the condition on p is sufficient in Theorem <ref>.
	
	
		All that is left is to stitch the above lemmas together: Let n = c2^k. Using Lemma <ref>, create a locally p-biased function g:-1,1^2^k→-1,1 on 2^k variables; then, using Lemma <ref>, extend it to a function f on n variables.
	
	
	
	
	
	

§ NON-ISOMORPHIC FUNCTIONS
 
	In this section we discuss the classes of non-isomorphic locally p-biased function.
	We show that for the hypercube of dimension n, the growth rate with respect to n is at least Ω(2^√(n)/√(n)) for p=1/2 and super-exponential for p=1/n, when such p's are permissible. We conjecture that for any permissible p the growth rate is super-polynomial.	
	
	The proof for p=1/2 is based on an explicit construction of non-isomorphic locally 1/2-biased functions.
	In order to define these functions we use the following simple proposition.
	
		Let f_i:{-1,1}^n_i→{-1,1} be locally 1/2-biased functions for i=1,2 where n_1+n_2=n. Then
		
    f(x)=f_1(x_1,...,x_n_1)f_2(x_n_1+1,...,x_n)

		is a locally 1/2-biased function on {-1,1}^n.
	
	
	
		Let x∈{-1,1}^n, let x' be a neighbor of x, and denote f(x)=f_1(x_1,…,x_n_1)f_2(x_n_1+1,…,x_n)=y_1· y_2 and f(x')=f_1(x'_1,…,x'_n_1)f_2(x'_n_1+1,…,x'_n)=y'_1· y'_2 . Then x' differs from x in either the first n_1 coordinates, or the last n_2 coordinates. If it differs in the first n_1 coordinates, then y'_2 = y_2. Since f_1 is locally 1/2-biased, there are exactly n_1/2 coordinate changes such that y'_1 = y'_2, yielding f(x') = 1. Similarly, if x' differs in the last n_2 coordinates, then y'_1 = y_1, and there are exactly n_2/2 coordinate changes such that y'_2 = y'_1, again yielding f(x') = 1. So overall, x has exactly n_1/2 + n_2/2 = n/2 neighbors where f is 1.
	
	
	The above proposition allows us to construct examples for locally 1/2-biased functions, by combinations of such functions on lower dimensions.

	
	We have two basic examples for locally 1/2-biased functions:
	
		
  * In any even dimension n,
		
    g_n(x_1,…,x_n)=x_1⋯ x_n/2.

		
  * 
		In dimension n=4,
		
    h(x_1,x_2,x_3,x_4)=1/2(x_1x_2+x_2x_3-x_3x_4+x_1x_4).

	
	
	The Fourier decomposition of a Boolean function is its expansion as a real multilinear polynomial: any Boolean function f:-1,1^n → can be written as a sum
	
    f(x_1,…,x_n) = ∑_S⊆1,…,nf̂_S ∏ _i∈ S x_i,

	where the f̂_S are real coefficients. Such a representation is unique; for a proof and other properties of the Fourier decomposition, see e.g chapter 1 in <cit.>. 
	
	Automorphisms of the hypercube are manifested on the Fourier decomposition of a Boolean function by either permutation or by a sign change to a subset of indices. Hence, we can show that two Boolean functions are not isomorphic by showing that their Fourier decompositions cannot be mapped into one another by such permutations and sign changes.
	
	In this section, a tensor product of two functions f(x_1, …, x_n) and g(x_1,…, x_m) is a function on disjoint indices, i.e. 
	
    h(x_1, …, x_n+m) = f(x_1,…,x_n)· g(x_n+1,…, x_n+m).

	
	 
		There exists h_1,h_2,… such that for any k the function h_k is locally 1/2-biased on the 4k-dimensional hypercube and h_k is not isomorphic to any tensor product of h_1,…,h_k-1,g_2,g_4,g_6,....
	
	
	
		We define h_1=h, and
		
    h_k=h(∏_i=0^k-1 x_1+4i,…,∏_i=0^k-1 x_4+4i),

		where h is the function from example <ref>.
		By Lemma <ref>, h_k is locally 1/2-biased on {-1,1}^4k.
		Assume that h_k is isomorphic to a tensor product of h_1,…,h_k-1,g_2,...,g_n-2, as in Proposition <ref>. If there exists 1≤ i ≤ j< k such that both h_i and h_j appear in a product that is isomorphic to h_k, then the Fourier decomposition of the product would have at least 16 different monomials. But h_k has only 4 different monomials, and the functions cannot be isomorphic. 
		Similarly, if we do not use any of the functions h_1,…,h_k-1, then we get the parity function, which has only one monomial in its Fourier decomposition.
		Hence, we may assume that there is only one 1 ≤ i<k such that h_i is in the product. Then, up to an automorphism, this function is of the form 
		
    f(x) = h_i(x_1,…,x_4i)g_4k-4i(x_4i+1,…,x_4k).

		On the one hand, by definition of h_k, its Fourier decomposition has pairs of monomials with no shared indices (e.g. the monomials that replace x_1x_2 and x_3x_4 in h_1).
		On the other hand, in the decomposition of f, all monomials have shared indices; for example x_4i+1 appears in all monomials. Hence they are not isomorphic.
	
	
	Using the functions h_1,h_2,… we can give a lower bound for the class of non-isomorphic locally 1/2-biased functions.
	
	 
		The number of non-negative integer solutions to
		
    a_1+2a_2+…+ka_k ≤ k

		is at least C4^√(k)/k^1/4, where C>0 is a universal constant.
	
	
	
		For any 1≤ℓ≤ k, the number of solutions to (<ref>) is at least the number of solutions to
		
    ℓ a_1+ℓ a_2+…+ℓ a_ℓ≤ k.

		It is well known that the number of solutions to this inequality is
		
    ℓ+k/ℓℓ.

		This term is maximized when ℓ^2 = k. Hence, a lower bound for the number of solutions to (<ref>) is
		
    2√(k)√(k).

		By Stirling's formula, the asymptotic of this is (1/√(π))4^√(k)/k^1/4.
	
	
	
		The number of integer solutions to the equality case is the famous partition function p(n).
		Hardy and Ramanujan <cit.> showed precise asymptotics. 
		Using their result it is possible to show that the number of integer solutions is
		
    ∑_j=1^k p(j) ∼ Ce^c√(k)/√(k),

		with explicit constants C,c>0. For our purposes, the simple estimation in Lemma <ref> is enough.
	
	
	 
		Let n be even. Let B_1/2^n be a maximal class of non-isomorphic locally 1/2-biased functions, i.e every two functions in B_1/2^n are non-isomorphic to each other. Then B_1/2^n≥ C2^√(n)/n^1/4, where C>0 is a universal constant.
	
	
	
		Let k=⌊ n/4⌋. By Proposition <ref>, we can construct locally 1/2-biased functions by tensor products of h_1,…,h_k and g_1,…,g_n, as follows: choose j functions h_i_j such that m := ∑ 4 i_j ≤ n. Then the tensor product ⊗ h_i_j uses m variables. This can be completed to n variables by tensoring with g_n-m.
						
		If two functions use the same h_i's, then they are isomorphic (by change of indices). And if they have a different decomposition of h_i's, then by the same arguments used in Proposition <ref>, they have a different Fourier decomposition and are therefore non-isomorphic. Thus, the isomorphic class of such a function is determined by the number of times each h_i appears in the product. 
		
		Hence, the number of non-isomorphic functions we can construct in this manner is the number of solutions to
		
    4a_1+8a_2+⋯+4ka_k ≤ n

		where the a_1,…,a_k are non-negative integers that represent the number of copies of h_i in the product. Using Lemma <ref>, this number is at least C4^√(k)/k^1/4=C'2^√(n)/n^1/4
	
	
	It should be noted that a locally 1/2-biased function has a natural condition on its Fourier decomposition.
	It might be possible to obtain better bounds on the number of non-isomorphic functions using this condition.
	
	
		Let f:{-1,1}^n→{-1,1} be a locally 1/2-biased function. Then the Fourier weight at degree n/2 is 1.
	
	
	
		Let A_n be the adjacency matrix of the hypercube. The map
		
    f→ (f(a_1),...,f(a_2^n)),

		where a_1,...,a_2^n are the vertices of the hypercube, is a bijection between locally 1/2-biased functions and the null space of A_n.	Since
		
    A_n=[ A_n-1     I;     I A_n-1 ],

		We have
		
    P_n(t)=P_n-1(t-1)P_n-1(t+1),

		where P_n is the characteristic polynomial of A_n. 
		For A_2 the eigenvalue 0 has multiplicity 2 and ± 2 has 1. Continuing by induction, the eigenvalues of A_m are -m, -m+2,...,m with multiplicities m0, m2,..., mm.	
		Hence, for even n the dimension of the null space is nn/2.
		For any S⊆{1,2,...,n} with S=n/2 we denote χ_S(x)=∏_i∈ Sx_i.
		These functions are all locally 1/2-biased, hence we can define the image in the null space by the bijection with v_S. Note that there are nn/2 such vectors, and they form an independent set. Hence the set {v_S}_S is a basis of the null set. By the bijection we get that every locally biased function is a linear combination of χ_S.
	
	
	Class sizes for locally 1/n-biased functions can also be achieved via the following proposition.
	
	 
		Let n=2^k, and let C_1 and C_2 be two non-isomorphic distance-3 perfect codes on the n-1-dimensional hypercube. Then the two functions f_1 and f_2 obtained by using C_1 and C_2 as the perfect codes in the proof of Lemma <ref> are non-isomorphic. 
	
	
	
		Suppose to the contrary that f_1 and f_2 are isomorphic, i.e there is an automorphism φ: -1,1^n→-1,1^n such that for all x ∈-1,1^n, we have f_1(x) = f_2(φ(x)). Denote by B =(y,1) ;  y∈-1,1^n-1 the n-1-dimensional hypercube obtained by fixing the last coordinate to 1, denote C = (y,1) ;  y ∈ C_2 and note that support(f_2|_B) = C by construction. Consider  φ|_B, the restriction of φ to B. This restriction is an isomorphism between B and some n-1-dimensional hypercube A contained within the n- dimensional hypercube. Any sub-hypercube of dimension n-1 is obtained from -1,1^n by fixing one of the coordinates to be either 1 or -1, and taking the span of all other coordinates. Then A must be spanned by the first n-1 coordinates, leaving the last coordinate fixed: otherwise, by construction of Lemma <ref>, the set A would contain two neighboring points x and x' that differ only in their last coordinate such that f_1(x) = f_1(x') = 1. This means there are y,y' ∈ C obeying φ(y) = x, φ(y') = x'; but this is a contradiction, since φ should preserve distances, and the distance between x and x' is 1 while the distance between y and y' is 3. So A = (y,b) ;  y ∈-1,1^n-1 for some b ∈-1,1. But then φ|_B is an isomorphism between C_1 and C_2, since C_1 is a perfect code in A and C_2 is a perfect code in B; a contradiction. 
	
	
	
		Let n=2^k. Let B_1/n^n be the class of non-isomorphic locally 1/n-biased functions. Then B_1/n^n is super-exponential in n.
	
	
	
		By Proposition <ref>, any lower bound on the number of non-isomorphic perfect codes on the n-1-dimensional hypercube gives a lower bound to the number of locally 1/n-biased functions on the n-dimensional hypercube. Recent constructions, such as in <cit.>, give a super-exponential lower bound on the number of such perfect codes.
	
	
	We would have liked to apply the same argument to locally m/n-biased functions, as given by the construction in Lemma <ref>. Our argument there used the explicit construction of the Hamming code which, being linear, was easy to modify in order to obtain functions with disjoint supports. Such is not the case for the construction of non-linear codes. However, we still believe that similar estimates are true for any permissible p.
	
	
		By Proposition <ref>, scenery reconstruction is impossible for even-dimensional hypercubes. 
	
	For odd dimensional hypercubes, on which there are no non-trivial locally biased functions, we use locally stable functions instead, as described in the next section.
	
	
	
	

§ LOCALLY P-STABLE FUNCTIONS

	Unlike locally p-biased functions, there is no restriction on permissible p values for locally p-stable functions:
	
		Let p = m/n for some m ∈0,1,…,n. Then the parity function on n-m variables, 
		
    f(x_1,…, x_n) = x_m+1 x_m+2… x_n

		is locally p-stable.
	

	Thus we will focus on the number of non-isomorphic pairs of locally stable functions. A negative result is attainable by a simple examination: 
	
	
		If p = 1/n or p = (n-1)/n, then the parity function is the only locally stable p-function on the hypercube, up to isomorphisms.
	

			
		We prove only for p = (n-1)/n; the proof for p=1/n is similar. 			
		
		We will show that f depends only on a single coordinate. Let x be an initial point in the hypercube and y its unique neighbor such that f(x) ≠ f(y). Denote the coordinate in which they differ by i. By local stability, every other neighbor x' of x has f(x') = f(x), and every other neighbor y' of y has f(y') = f(y).		
		
		Let j≠ i, let x̃ be the neighbor of x that differs from x in coordinate j, and let ỹ be the neighbor of y that differs y in coordinate j. Then x̃ is a neighbor of ỹ, since x̃ and ỹ differ only in the i-th coordinate. Also, since f(x) = f(x̃) and f(y) = f(ỹ) but f(x) ≠ f(y), we have f(x̃) ≠ f(ỹ). 
		
		Since f is locally (n-1)/n-stable, each of x's neighbors x' has exactly one neighbor y' on which f attains the opposite value. By the above, for each such x', the corresponding y' differs from it in the i-th coordinate. This reasoning can be repeated, choosing a neighbor of x as the initial starting point, showing that for all x' with the same i-th coordinate as x, f(x) = f(x'), while for all x' that differ in the i-th coordinate from x, f(x) ≠ f(x'). This means that either f(x) = x_i or f(x) = -x_i.
	
	
	
	
	Many other p values, however, have larger classes of non-isomorphic locally p-stable functions, since locally stable functions can be built out of locally 1/2-biased functions:
	
	 
		Let n > 0 be an even integer. For every locally 1/2-biased function f on the n-dimensional hypercube, there exists a locally (n/2)/(n+1)-stable function f' on the n+1-dimensional hypercube. Further, if f and g are two non-isomorphic locally 1/2-biased functions, then f' and g' are also non-isomorphic. 		
	

	
		Define f' by		
		
    f'(x_1,…,x_n+1) = f(x_1,…, x_n) · x_n+1.
		
		Let x ∈-1,1^n+1 be a point in the n+1-dimensional hypercube. Since f is locally 1/2-biased, the function f' attains the value 1 on exactly half of x's neighbors which differ from x in one of the first n coordinates, and the value -1 on the other half of these neighbors. Alternatively, f' retains its value on exactly half of the neighbors which differ in the first n coordinates. For the neighbor that is different from x in the last coordinate, though, f' flips its sign. Therefore f' retains its value on a (n/2)/(n+1) fraction of x's neighbors, so f is locally (n/2)/(n+1)-stable.
		
		The claim about non-isomorphism follows directly from the functions' Fourier decomposition.		
	

	Observe that unlike locally biased functions, locally stable functions can be easily extended to higher dimension:
	
	 
		Let f be a locally (n-m)/n-stable function. Then f can be extended to hypercubes of size n' ≥ n by simply ignoring all but the first n coordinates. This gives a locally (n'-m)/n'-stable function.
	

	We can use this observation to give a lower bound on the number of locally (n'-m)/n'-stable functions for a fixed m and any n' ≥ 2m-2. 
	This works as follows: first, pick any fixed m>1. Using Proposition <ref>, we obtain a locally (n-m)/n = (n/2)/(n+1)-stable with n = 2m - 2. This can be extended by Observation <ref> to any n'≥ n, and together with Proposition <ref> we get a lower bound of C2^√(2m-2)/(2m-2)^1/4 different locally (n'-m)/n'-stable functions. 
	
	This observation also provides us with a pair of non-isomorphic locally stable functions for all hypercubes of dimension n≥ 5, showing that:
	
		Scenery reconstruction is impossible for n-dimensional hypercubes for n≥5.
	
	

	
	
	

§ OTHER DIRECTIONS AND OPEN QUESTIONS

	In this section we discuss similar results and questions for other graphs. We also list some further questions regarding locally biased and locally stable functions on the hypercube.	For other excellent open problems see <cit.>.
	
	

 §.§ Hypercube reconstruction

	Our work shows that in general, Boolean functions on the hypercube cannot be reconstructed.
	
	
		Under which conditions is it possible to reconstruct Boolean functions on the hypercube? 
	

	
		Is a random Boolean function reconstructible with high probability?
	

	
		Using the techniques of <cit.>, it can be shown that reconstruction is always possible in the hypercube of dimension at most 3.
	
	
	

 §.§ Other graphs

	
	Note that the necessity condition on p of Theorem <ref> can be applied to any finite regular graph, ruling out functions based on the relation between the graph degree and the number of vertices. 
	
	

 §.§ Trees

	Let G be an n-regular infinite tree. Then for any p = b/n, b = 0,1,…,n there exists a locally p-biased function. Such a function can be found greedily by picking a root vertex v ∈ G, setting f(v) = 1, and iteratively assigning values to vertices further away in any way that meets the constraints. 
		
	Notice that the method above requires picking some initial vertex, and that the method yields many possible functions on labeled trees (all of which are isomorphic when we remove the labels). Once the initial vertex v has been fixed, it is possible to generate a distribution on locally p-biased functions, by setting	f(v) to be 1 with probability b/n, and randomly expanding from there.
			
	
		For an n-regular tree G, find an invariant probability measure on locally p-biased functions that commutes with the automorphisms of the tree. 
		

	

 §.§ The standard lattice

	
			
	
	The following propositions show that there is a one-to-one mapping of locally p-biased functions from the hypercube to ^n. Since automorphisms of the lattice can be pulled back to automorphisms of the hypercube, we get lower bounds for the size of non-isomorphic locally p-biased functions on ^n.
	
	
		Let f:{-1,1}^n→{-1,1} be a locally p-biased function. 
		Then there exists a locally p-biased extension f̃:^d→{-1,1} such that .f|_{-1,1}^n=f. In addition, if f and g are non-isomorphic locally p-biased functions on the hypercube, then f̃ and g̃ are non-isomorphic.
	
	
	
		Here we think of the hypercube as {0, 1}^n instead of {-1,1}^n.
		Let 
		
    ψ(x_1,…,x_n)=(x_1 mod 2,…,x_n mod 2).
 
		For any t=(t_1,…,t_n)∈^n define Q_t=t+{0,1}^n. Then the set ψ(Q_t) is the hypercube {0, 1}^n. Moreover, there exists an automorphism φ of the hypercube, such that φ(ψ(Q_t))=Q_t-t.
		We define
		
    f(x)=f(ψ(x)).

		Suppose that f is locally p-biased function on the hypercube. Note that .f|_Q_t is locally p-biased on Q_t for any t∈^n. 
		Let x∈^n. Consider Q^+=Q_x and Q^-=Q_x-e, where e=(1,…,1).
		Then, Q^+∩ Q^- = {x} and the neighbors of x are partitioned such that half of them are in Q^- and the other half are in Q^+.
		Since .f|_Q_x^± is locally p-biased, out of the n neighbors of x in Q^+ on exactly pn the value of f is 1, and the same holds true for Q^-. Thus, f is locally p-biased function on ^n.

		Note that the automorphisms of ^n are those of the hypercube with the addition of translations.
		Since there exists an isomorphism between any two hypercubes in the tiling (the above mentioned φ), any automorphism between f and g would induce one between f and g.
	
	
	The above extension procedure gives us lower bounds on the growth rate of some classes of non-isomorphic locally p-biased functions.
	
	
		Let B_p^n be the class of non-isomorphic locally p-biased functions on ^n. 
		
			
  * If n is even, then |B_1/2^n| ≥ C2^√(n)/n^1/4, where C>0 is a universal constant.
			
  * If n=2^-m, then B_1/n^n is super-exponential.
		
	

	Unlike for the hypercube, we do not have a characterization theorem for the lattice ^n. In fact, we have found a locally 1/2-biased function for  and a locally 1/4-biased function for ^2; see Figure <ref>. Both of these are not the result of embedding the relevant hypercube in the lattice via Proposition <ref>. 
	
	
	Give a complete characterization of permissible p values for locally p-biased functions on ^n. When such functions exist, count how many there are.
	

	

 §.§ Cayley Graphs

	In general, for a given group with a natural generating set, it is interesting to ask whether its Cayley graph admits locally biased or locally stable functions, and if so, how many. Specific examples which spring to mind for such groups are the group of permutations S_n with either all transpositions σ_ij_i<j, and  with any number of generators. For the latter case, the following observation shows that for any two generators,  has a locally 1/2-biased function:
	
		
	Let a > 1 and b > 1 generate . Then the function f defined by 
		
    f(x) = 
    		
    		1,     0 ≤ (x  2(a+b)) < a+b  
    
    		-1,     a+b ≤ (x  2(a+b)) < 2(a+b)
	
	is locally 1/2-biased.
	
	
	Computer search shows that for some generators, other locally biased functions exist; see Figure <ref> for an example.

	
		Characterize the locally biased and locally stable functions on S_n as a function of its generating set.
	
	
	
		Characterize the locally biased and locally stable functions on  as a function of its generating set.
	

		

	

 §.§ Locally biased and locally stable functions

	Section  <ref> only gives lower bounds on the number of locally biased functions, and applies only for p=1/2 and p = 1/n (and 1-1/n by taking negation of functions).
	
	
		What are the exact asymptotics for the number of non-isomorphic locally biased functions, for all permissible p?
	
	
	We can also ask about the robustness of the locally biased property:
	
	
		How do the characterization and counting theorems for locally biased functions change, when we relax the locally biased demand for 2^o(n) of the vertices (i.e a small amount of vertices can have their neighbors labeled arbitrarily)?
	

	The uniqueness of locally 1/n-stable functions is in stark contrast to the exponential size of locally 1/n-biased functions. Our bounds in section  <ref> for the number of (n-m)/n-locally stable functions are exponential in m, but not in n. We seek a better understanding of these functions:
	
	
		What are the exact asymptotics for the number of non-isomorphic locally stable functions?
	

	
	
	

§ ACKNOWLEDGMENTS

	We thank Itai Benjamini for proposing the question of indistinguishability and for his advice, Ronen Eldan for his suggestions on locally stable functions, and David Ellis for the connection to perfect codes. We also thank Noga Alon and Peleg Michaeli for some useful discussions.
	
	
	
	plain
	
	
