Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am given two sequences of multivariate polynomials $\overline{p}=(p_1,p_2,\dots,p_k)$ and $\overline{q}=(q_1,q_2,\dots,q_k)$, all of them on the variables $x_1,\dots,x_n$ over some finite field $\mathbb{F}$ ($\mathbb{F}_2$, if one needs to be concrete).

Every random choice of values for $x_1,\dots,x_n$ yields a vector $v_p\in\mathbb{F}^k$ and a vector $v_q\in\mathbb{F}^k$. Hence we have two distributions $D_{p}$ and $D_{q}$ over vectors from $\mathbb{F}^k$. Assume that the distributions are distinct.

My goal is to find (algorithmically, not just prove existence) a vector $w\in\mathbb{F}^k$ such that the distributions induced by the inner product $w\cdot \overline{p}$ and $w\cdot\overline{q}$ are still distinct.

($w\cdot\overline{p}=\sum_{i=1}^k w_i\cdot p_i(x_1,\dots,x_n)$ and so this is a multivariate polynomial taking values in $\mathbb{F}$ and so inducing a distribution on $\mathbb{F}$)

share|improve this question
    
Are you also (though not mainly) interested in a proof that this is possible? Do you have one? –  joriki Jul 24 '11 at 11:22
    
I was told there is a nonconstructive proof at least for $F_2$ using discrete Fourier analysis. I have not seen it myself and I don't even want to assume it's correct (it will be interesting to find out that this is not always possible). –  Gadi A Jul 24 '11 at 12:05
    
I think I have an algorithm that would be more efficient than brute-force enumeration if $k\gg n$ -- would that be of use? –  joriki Jul 24 '11 at 12:07
    
I'll be glad to hear it, even if it's not the solution I need yet. –  Gadi A Jul 24 '11 at 12:22
1  
I should add that this seems to be a very different (and in fact, simpler) problem if you want to distinguish the distribution of $w \cdot (\overline p - \overline q)$ from the deterministically zero distribution. Schwartz-Zippel comes to mind. –  Srivatsan Jul 24 '11 at 20:22

1 Answer 1

up vote 2 down vote accepted

This answer deals only with the aspect of distinguishing different distributions over $\mathbb F^k$ using the dot product with a vector $w$; I haven't looked into how to make use of the fact that the distributions are generated by polynomials. So you can use this to distinguish arbitrary distributions (in fact, arbitrary complex-valued functions on $\mathbb F^k$), but there might be better solutions that make use of the polynomials. That means also that, compared to a brute-force solution by enumeration, which would take $O(|\mathbb F|^n+|\mathbb F|^{2k})$ time, I'm only reducing the $O(|\mathbb F|^{2k})$ complexity of trying out all possible $w$, not the $O(|\mathbb F|^n)$ complexity of substituting all possible arguments into the polynomials, so this will only be useful if $2k\gtrsim n$.

I'll provide an $O(|\mathbb F|^k)$-time algorithm to find a suitable $w$ to distinguish two distinct complex-valued functions on $\mathbb F^k$; in justifying the algorithm I'll also be proving that such a $w$ always exists.

Given two distinct complex-valued functions $g$ and $h$ on $\mathbb F^k$, form $f=g-h\neq0$. The goal is to find $w\in\mathbb F^k$ such that

$$f_w(y)=\sum_{\scriptstyle x\in\mathbb F^k\atop\scriptstyle w\cdot x=y}f(x)$$

is non-zero for some $y\in\mathbb F$. For given $w\neq0$ and $y$, the condition $w\cdot x=y$ picks out a $(k-1)$-dimensional affine subspace of $\mathbb F^k$. More generally, for $V$ any affine subspace of $\mathbb F^k$, let

$$f_V=\sum_{x\in V}f(x)\;.$$

Now let $W$ be any affine subspace of $\mathbb F^k$, and for $\dim W<d<k$ consider

$$\sigma_W^d=\sum_{\scriptstyle V>W\atop\scriptstyle\dim V=d}f_V=\sum_{\scriptstyle V>W\atop\scriptstyle\dim V=d}\sum_{x\in V}f(x)\;,$$

where $V>W$ means that $W$ is a proper affine subspace of $V$. By symmetry, each $x\in W$ occurs the same number $c_1$ of times in this sum, and each $x\notin W$ occurs the same number $c_2$ of times, with $c_2\lt c_1$, so we have

$$\sigma_W^d=c_1\sum_{x\in W}f(x)+c_2\sum_{f\notin W}f(x)=(c_1-c_2)\sum_{x\in W}f(x)+c_2\sum_{f\in\mathbb F^k}f(x)=(c_1-c_2)f_W+c_2f_0(0)\;.$$

The second term vanishes if $g$ and $h$ are normalized distributions; if they are arbitrary functions, we can calculate it (in $O(|\mathbb F|^k)$ time) and use $w=0$ if it is non-zero. Thus we may assume that $\sigma_W^d$ is a non-zero multiple of $f_W$. It follows that if $f_W\neq0$ for some $W$, then for any $d>\dim W$ at least one affine subspace $V>W$ with $\dim V=d$ must have $f_V\neq0$, since the sum of all these is a non-zero multiple of $f_W$.

This suggests the following algorithm. Find some $x\in\mathbb F^k$ with $f(x)\neq0$, and set $W_0=\{x\}$. In step $d$, calculate $f_V$ for all $V>W_{d-1}$ with $\dim V=d$, and choose $W_d$ among them such that $f_{W_d}\neq0$. By the above, this is always possible, since $f_{W_{d-1}}\neq0$. Then $W_{k-1}$ is a $(k-1)$-dimensional affine subspace of $\mathbb F^k$, and we can find $w\in\mathbb F^k$ and $y\in\mathbb F$ such that $f_w(y)=F_{W_{k-1}}\neq0$.

The search for $x$ takes $O(|\mathbb F|^k)$ time. In step $d$, there are $(|\mathbb F|^{k-d+1}-1)/(|\mathbb F|-1)\in O(|\mathbb F|^{k-d})$ affine subspaces to consider, and in a naive implementation $|\mathbb F|^d$ function values have to be summed for each, taking $O(|\mathbb F|^k)$ time per step. Since all steps after step $d$ sum only over complete cosets of $W_d$, an easy optimization would be to reduce the dimension by $1$ in each step by summing over these cosets and then working in the quotient space. The naive implementation would take $O(k|\mathbb F|^k)$ time in total; the optimization reduces this to $O(|\mathbb F|^k$). In practice, one would typically find a non-zero sum long before all affine subspaces have been searched, so the average performance may be considerably better than this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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