2
$\begingroup$

This is a homework question, so I'm not looking for answers, just general guidance.

I'm looking at a Sublinear Algorithms survey where (Group) Homomorphism property testing is discussed. The case of homomorphisms from $\left(\mathbb{Z}_{n}, +\right)$ to $\left(\mathbb{Z}_{n}, +\right)$ (where + is the modulo addition) in particular.

Since $$f:\mathbb{Z}_{n}\to\mathbb{Z}_{n}\ is\ a\ homomorphism\iff\forall x\in\mathbb{Z}_{n}:\ f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$$ (I've managed to prove that), it is suggested to property test $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$.

To counter that suggestion it is said that for a sufficiently large $n$, $$f:\begin{array}{lll} \mathbb{Z}_{n} & \to & \mathbb{Z}_{n}\\ x & \mapsto & x\ \left(mod\ \left\lceil \sqrt{n}\right\rceil \right) \end{array}$$ maintains $f\left(x+1\right)\equiv_{n}f\left(x\right)+f\left(1\right)$ for $1-\frac{1}{\sqrt{n}}$ fraction of the $x\in\mathbb{Z}_{n}$ (managed to prove that), but that $f$ is $1-\frac{1}{\sqrt{n}}$-far from any homomorphism (where $\epsilon$-far means that in order to get a homomorphism out of $f$ we have to change at least $\epsilon n$ outputs of $f$).

We're asked to show a counter example of a function that passes the test for $1-o\left(1\right)$ fraction of the inputs, but is $\frac{1}{100}$-far from homomorphisms, which is a bit easier.

So I wanted to show $f$ as my example. I managed to prove what I wrote so far, but I'm still trying to prove $f$ is $1-\frac{1}{\sqrt{n}}$-far.

What I've tried:

Assume by contradiction that $\delta\left(f\right)<n-\sqrt{n}$ (where $\delta\left(f\right)$ is the distance from homomorphisms), that is there exists $h$, an homomorphism, with less than $n-\sqrt{n}$ different (compared to $f$) outputs.

I've divided into 2 cases.

First case is $h\left(1\right)=f\left(1\right)$ which means $h\left(1\right)=1$. It is easy to get a contradiction this way, since then there exists $x>\sqrt{n}$ such that $h\left(x\right)=f\left(x\right)$ (otherwise, contradiction to $\delta\left(f\right)<n-\sqrt{n}$). Since $h$ is a homomorphism, we get $$h\left(x\right)=\underset{i=1}{\overset{x}{\sum}}h\left(1\right)=\underset{i=1}{\overset{x}{\sum}}1=x\neq f\left(x\right)$$

Now the other case where $h\left(1\right)\neq f\left(1\right)$ is where I'm stuck. It's hard for me to get intuition since apparently this is only true for large $n$'s, which makes it hard to look at basic examples. I'm not even sure dividing to these cases is the best approach, and would love some help. Thanks!

Edit:

As requested, a link to the survey by Ronitt Rubinfeld. Only managed to find it in ps format.

$\endgroup$
  • $\begingroup$ Added the "$$". Thanks for the suggestion. I thought StackExchange doesn't like links since they break, but since you asked I will. $\endgroup$ – Ungoliant Jan 5 at 20:46
  • $\begingroup$ Added a link to the survey. $\endgroup$ – Ungoliant Jan 5 at 20:50
  • $\begingroup$ As you mentioned, no, we do not like links when we have to check the link in order to understand a question or answer. We would like to see that questions are standalone. However, it is always helpful if there are links available that can provide some context such as where the problem comes from, what is level of knowledge expected, what are the relate stuff, how much is solved or not, etc. Those context will usually be very helpful to draw more better answers faster. $\endgroup$ – Apass.Jack Jan 5 at 20:51
  • $\begingroup$ In fact, when a post is decorated with pertinent links, it help me consider it as a better post and the writer is academically more mature. $\endgroup$ – Apass.Jack Jan 5 at 20:56
  • 1
    $\begingroup$ You can calculate the distance from the identity directly. For any other homomorphism, $h(x+1)-h(x)\neq1$, whereas for your function it’s the typical case. So your function and $h$ disagree on at least half the inputs (roughly). $\endgroup$ – Yuval Filmus Jan 5 at 21:04
1
$\begingroup$

Thanks to the help in the comments I was able to unfixate and find an answer to the question. I prove $\delta\left(f\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$.

Let $h:\mathbb{Z}_{n}\to\mathbb{Z}_{n}$ be an homomorphism.

• If $h\left(1\right)=f\left(1\right)$ then $h\left(1\right)=1$ and h is the identity function, since $h\left(0\right)=0$ and $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ due to homomorphisms definition and properties. We get $\delta\left(f,h\right)=1-\frac{1}{\sqrt{n}}\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$ (since they disagree on $n-\sqrt{n}$ values).

• Otherwise, $h\left(1\right)\neq f\left(1\right)$, that is $h\left(1\right)\neq1$. Assume by contradiction that exists $x\in\mathbb{Z}_{n}$ such that $h\left(x+1\right)=h\left(x\right)+1$, but due to homomorphisms definition we get $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ which is a contradiction to $h\left(1\right)\neq1$. Since our function $f$ maintains that $$h\left(x+1\right)=h\left(x\right)+1$$ for $x\in\mathbb{Z}_{n}\backslash\left\{ q\sqrt{n}|0\leq q\leq\sqrt{n}-1\right\}$ , which means $n-\sqrt{n}$ “bad” pairs of $x$ and $x+1$. This means that in order to get any homomorphism, including $h$, we have to change at least one value for each pair, which means at least $\frac{\sqrt{n}-1}{2}$ values changed for each interval $\left[q\sqrt{n},\left(q+1\right)\sqrt{n}\right)\cap\mathbb{Z}_{n}$ (where $0\leq q\leq\sqrt{n}-1$), otherwise due to to the pigeonhole principle we have two consecutive values that are unchanged which is again a contradiction since then $h\left(x+1\right)=h\left(x\right)+1$. So in total we have at least $$\sqrt{n}\frac{\sqrt{n}-1}{2}=\frac{n-\sqrt{n}}{2}$$ values changed, which means $$\delta\left(f,h\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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