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.

Let $v$ be a binary vector of dimension $n$. Assume that $n$ is a perfect square, then $v$ can be thought of as a function $f:[\sqrt n]\times[\sqrt n]\to \{0,1\}$, where $[\sqrt n]=\{1,\ldots,\sqrt n\}$. Choose a prime $q\in[n,2n]$, then it is well known(*) that $f$ has a unique extension $\tilde f:\mathbb{F}_q^2\to\mathbb{F}_q$ as a degree $\sqrt n -1$ polynomial.

How do I explicitly construct this polynomial ?

(*) For reference see Section 7.2 (page 37) in: http://www.scottaaronson.com/papers/alg.pdf

share|improve this question
    
@JyrkiLahtonen I believe it is a fairly standard notation in theoretical computer science and combinatorics –  Tom Oct 7 '11 at 17:01
    
Well, why is there a square root in the notation? –  mixedmath Oct 7 '11 at 17:03
    
@Tom: For sake of convenience you should say that the dimension is $k^2$, and use $k$ instead of $\sqrt n$. It is clearer and nicer when working with integers. –  Asaf Karagila Oct 7 '11 at 17:05
1  
And I think that this is false. But IMHO the usual convention is that the degree of the monomial $x^iy^j$ is $i+j$. If you have adopted the convention that the degree of $x^iy^j$ is $\max\{i,j\}$, then there is hope :-) –  Jyrki Lahtonen Oct 7 '11 at 17:05
    
@AsafKaragila In general, I agree with you - but I've wanted to be consistent with the reference I supplied. –  Tom Oct 7 '11 at 17:07

1 Answer 1

up vote 2 down vote accepted

Is the following not a counterexample, if we follow the (IMHO) standard agreement that $\deg x^iy^j=i+j$?

Let $n=4$, $q=5$. This time $\sqrt{n}-1=2-1=1$ so we are looking for a linear polynomial. So we have $f(x,y)=ax+by+c$. If we specify $f(1,1)=f(1,2)=f(2,1)=0$, then we have $$ 0=a+b+c=a+2b+c=2a+b+c, $$ so the only solution to these three equations is $a=b=c=0$. So if we also insist that $f(2,2)=1$, then $f$ cannot be linear.

===============================

OTOH, if we declare that $\deg x^iy^j=\max\{i,j\}$, then we can do Lagrange interpolation in two steps. Let us for each $j\in [\sqrt n]$ find a polynomial $f_j(y)\in F_q[y]$ such that $\deg f_j(y)=\sqrt n-1$, $f_j(j)=1$ and $f_j(i)=0$ for all $i\in[\sqrt n], i\neq j$. This is just usual Lagrange interpolation. We can let $$ f_j(y)=K_j\,\frac{(y-1)(y-2)\cdots (y-\sqrt n)}{y-j} $$ for an appropriate constant $K_j\in F_q^*$

Then as a next step let's for all $j\in[\sqrt n]$ find a polynomial $g_j(x)\in F_q[x]$ such that for all $i\in[\sqrt n]$ we have $g_j(i)=f(i,j)$. Again, Lagrange interpolation tells that such a polynomial $g_j(x)$ exists and is of degree $\le \sqrt n -1$, because its value was specified at $\sqrt n$ points.

Putting all this together we get a bivariate polynomial $$ h(x,y)=\sum_{k\in[\sqrt n]} g_k(x) f_k(y)\in F_q[x,y] $$ that has the prescribed value at all the points $(i,j)\in[\sqrt n]\times [\sqrt n]$. Furthermore, all the monomials $a_{ij}x^iy^j$ of $h(x,y)$ have $i,j\le\sqrt n-1$.

=============================

Edit: At some point I had a suspicion that a required polynomial $h(x,y)$ extending the given function $f$ at the given set $S$ of $n$ points on the plane could be found within the span of any $n$ monomials $x^iy^j, i,j<q$. A moment's reflection shows that as the $x$-coordinates of the points of $S$ are constrained to a set of size $\sqrt n$, we can write the restriction of any higher power $x^i$ function to the set $S$ to lower degree terms. The recipe is simply to replace $x^i$ with its remainder when divided by the polynomial $(x-1)(x-2)\cdots (x-\sqrt n)$ that vanishes on all of $S$. Similarly for the $y$ variable.

OTOH we clearly need an $n$-dimensional space of polynomials to extend all the functions with prescribed values on a set of $n$ points. Therefore to be able to extend all the functions we are forced to use all the polynomials in the linear span of $\{x^iy^j\mid 0\le i,j <\sqrt n\}$. The restriction to functions with the property $f(S)\subseteq \{0,1\}$ does not change this fact, because within that set we can find an obvious set of $n$ linearly independent functions.

share|improve this answer
    
I'm not sure, but isn't the fact we are over a finite field might allows a solution other than $a=b=c=0$ ? –  Tom Oct 7 '11 at 17:19
    
@Tom: No. Subtracting the equation $a+b+c=0$ from the equation $a+2b+c=0$ gives us $b=0$. Similarly subtracting it from the equation $2a+b+c=0$ implies $a=0$. Finally, plugging these values to the equation $a+b+c=0$ implies $c=0$. The theory of linear systems of equation stays the same over any field. –  Jyrki Lahtonen Oct 7 '11 at 17:29
    
Corrected the definition of $f_j(y)$. Apparently I have a hard time getting it out of my system that $0\notin [\sqrt n]$. –  Jyrki Lahtonen Oct 7 '11 at 17:32
    
Yes, you're right. –  Tom Oct 7 '11 at 17:32
1  
@Tom: I'm not quite sure. It may be possible to get a lower 'standard degree' polynomial representing that function by using also monomials of the form $x^iy^j$ where either $i$ or $j$ is larger than $\sqrt n$ but the total degree $i+j$ is less than $2\sqrt n -2$. IOW the double Lagrangian interpolation above is not guaranteed to produce the lowest total degree polynomial extendinf the function $f$. –  Jyrki Lahtonen Oct 7 '11 at 17:49

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.