5
$\begingroup$

I recently posted this question on MSE. While it attracted interest, no answers were submitted, so I thought to try and post it here.

I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following:

Given an even number $m$, the device runs over all closed walks of length $m$ that start and end at the origin. After going through all possible walks, the device gives me a list of all sums of the values of $f$ along each of these walks (without saying which sum corresponds to which walk). This list could potentially have repetitions of course (if I get the same sum from more than one walk).

To clarify, for me a closed walk of length $m$ is an ordered list of $m+1$ vertices, such that each two vertices in the list are adjacent to one another (and two lattice points are adjacent if they differ by 1 in exactly one of their components). In our case, the first and last vertices on the list are the origin.

Here is an example (showing only part of the infinite lattice):

enter image description here

Here, red points correspond to the value $1$ and blue points to the value $0$.

If I take $m=0$, the only closed walk at the origin is the one starting and ending there without moving (and the sum along this walk is $1$), and so the device would return the list $(1)$. This measurement allows me to deduce that $f(1,1)=1$.

If $m=2$, I have two closed walks of length $2$ - going up and back, or going right and back. The list of sums along these walks are $(3, 2)$ (but again - I don't know which sums corresponds to which walk). Since I know that the value at the origin is $1$, I can tell that either $f(1,2)=1, f(2,1)=0$ or vice versa. Personally I only care about $f$ up to reflection, so I'm fine with assuming WLOG the first option and continuing.

The question is, can I continue this process in a way which will definitely allow me to recover $f$ at an arbitrary point away from the origin? (up to reflection)

The difficulty comes from the fact that this list of sums becomes more and more complicated (you have more and more closed walks, and they are more complex). Since I know only sums (up to multiplicity) but not which closed walks a given sum corresponds to, it's hard to recover the value at a specific point. I can use slightly more sophisticated arguments with $m=4$ to also obtain the values of $f$ one step further away from the origin (this already requires splitting into several cases and is not very elegant), but when moving to $m=6$ and more I am no longer sure how to recover the values of $f$ at each point (if that's even possible).

So the question is - can this be done? Is there an algorithm? Will it help if I can add finitely many "devices" at points that I choose? (not just one at the origin)

Hard mode - can you take the lattice $\mathbb Z^2$? Can you do this for dimension higher than $2$?

Any help would be appreciated. Thanks in advance.

Improve this question
$\endgroup$
12
  • $\begingroup$ The origin is not in (1,1)! $\endgroup$
    – domotorp
    Commented Jan 13 at 9:44
  • 2
    $\begingroup$ One interesting special case, when (a) and (b) are equivalent, would be when $f$ vanishes at all vertices at distance strictly less than $m/2$. Here the question becomes equivalent to whether there is a non-trivial $\pm 1$ combination of the squares of the binomial coefficients in row $m/2$ that sums to zero. I have verified by computer that there is no such combination for $m\le 40$. $\endgroup$
    – domotorp
    Commented Jan 13 at 10:21
  • 1
    $\begingroup$ It does seem natural to start by considering the special case where you know that there is some $k\in\mathbb{N}$ such that $f(x,y)=1$ implies $x+y=k$. That is, all the nonzero values of $f$ lie on the line $x+y=k$ for some fixed $k$ (whose value you can assume you know, since you can figure it out even if you don't know it a priori). If the problem is intractable even in this special case, then the more general question has to be intractable. $\endgroup$
    – Timothy Chow
    Commented Jan 14 at 12:51
  • 1
    $\begingroup$ Indeed it is not! Instead, we need to allow also zero coefficients. Anyhow, it is based on that if $S$ is the collection of indices where you have 1 at $(s,k-s)$, then the number of length $2k$ paths will be $\sum_{s\in S} (\binom ks)^2$. If every such number is unique, then we can recover the value of $S$, apart from reflecting some values to the diagonal. I've verified this new variant for $k\le 9$. $\endgroup$
    – domotorp
    Commented Jan 15 at 20:10
  • 1
    $\begingroup$ And maybe your reflection to the diagonal was more restrictive, and you want to allow to reflect only the entire $S$, and not the values one-by-one, but in case of variants (a) and (b), we cannot hope for that. $\endgroup$
    – domotorp
    Commented Jan 15 at 20:12

0

Reset to default

You must log in to answer this question.