<p>Let $F(x) = \displaystyle\sum_{i=0}^{n-1}a_{i}x^{i}$, $G(x,y) = \displaystyle\sum_{i=0}^{n_{x}-1}\sum_{j=0}^{n_{y}-1}a_{ij}x^{i}y^{j} \in \mathbb Z[x,y]$ with $a_{i},a_{ij} \in [0,p-1]$ for some prime $p$. Let $F(q) = f_{q}$, $G(q,r) = g_{qr}$ for distinct primes $q,r \ge p $.</p>

<p>$a_{i}$ can be got from $f_{q}$ by mod $q$, subtraction, divide by $q$ operations. But the technique will fail for $g_{qr}$.</p>

<p>$q=5$, $r=7$, $p=3$. $G_{1}(x,y)=xy$, $G_{2}(x,y)=x^{2} + 2x$. $G_{1}(q,r) = 35 = G_{2}(q,r)$ - <a href="https://mathoverflow.net/users/4953/wadim-zudilin">Wadim Zudilin</a>.</p>

<p>Can knowing $G(x,y)$ at more pairs $(q_{k},r_{k})\_{k=1}^{m}$ where $p^{n_{y}} &gt; q_{k} &gt; p$ and $p^{n_{x}} &gt; r_{k} &gt; p$ help? - <a href="https://mathoverflow.net/users/3455/gerhard-paseman1.">Gerhard Paseman</a>.</p>

<p>$(1)$What is the minimum such $m$? Does $m$ depend on $n_{x}$ and $n_{y}$?</p>

<p>$(2)$What is the algorithm to extract $a_{ij}$? </p>

<p>For $H(x_{1},\cdots,x_{t}) \in \mathbb Z[x_{1},\cdots,x_{t}]$, </p>

<p>$(A)$What is $m_{t,n_{x_{i}}}$ - the minimum number of tuples, one should evaluate $H(x_{1},\cdots,x_{t})$?</p>

<p>$(B)$What is the algorithm to extract the coefficients?</p>

<p>$(C)$Is the growth in $m_{t,n_{x_{i}}}$ logarithmic or linear or polynomial with respect to $t$ and $n_{x_{i}}$?</p>

<p>$\underline{Note}$: $m=1$ is trivially possible if one of $r$( or $q$) is greater than $p^{n_{x}}$( or $p^{n_{y}}$) and the other less than $p^{n_{y}}$( or $p^{n_{x}}$) but both greater than $p$.</p>

<p>I am facing a major hurdle in a critical step in matrix multiplication. If I can control the prime size to be of similar size, if $m$ is independent of $n$ or behaves logarithmically or linearly with $n$, and if I can extract the coefficients using mod operations quickly, then I have a chance of showing matrix multiplication is in $O(n^{2+\epsilon})$ complexity. My hurdle is in the bivariate case ($t=2$). I posted the generalization for arbitrary $t$ as well as the problem generalized.</p>

<p><a href="https://mathoverflow.net/questions/42846/shorter-version-of-computational-number-theory-problem">https://mathoverflow.net/questions/42846/shorter-version-of-computational-number-theory-problem</a></p>

CC BY-SA 2.5
2010-10-19T21:54:37.763Z
apart from the formatting nightmare this question is, it sounds like this is a cross post from MO. please add in the link to the original post.
Suresh Venkat
CC BY-SA 2.5
2010-10-19T22:00:19.407Z
Motivation would help. Tell us why we should care.
Warren Schudy
CC BY-SA 2.5
2010-10-20T00:11:14.080Z
added the motivation in the end.
Turbo
CC BY-SA 2.5
2010-10-20T01:00:05.800Z
Please stop asking one question at more than one place at the same time.  http://mathoverflow.net/questions/42740/computational-number-theory-problem
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-20T01:19:29.803Z
@Tsuyoshi: I'm not sure why this is an issue in general, as long as the cross-posting is transparent.
arnab
CC BY-SA 2.5
2010-10-20T01:22:50.727Z
@arnab: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-20T01:54:02.727Z
ok thank you Tsuyoshi
Turbo
CC BY-SA 2.5
2010-10-20T01:55:51.070Z
How do I close this?
Turbo
<cc.complexity-theory><nt.number-theory><algebraic-complexity>
Algorithmic Number Theory Problem - related to Matrix Multiplication Complexity
Turbo
# Algorithmic Number Theory Problem - related to Matrix Multiplication Complexity

(Asked by: username_0 on 2010-10-19)

Let $F(x) = \displaystyle\sum\_{i=0}^{n-1}a\_{i}x^{i}$, $G(x,y) = \displaystyle\sum\_{i=0}^{n\_{x}-1}\sum\_{j=0}^{n\_{y}-1}a\_{ij}x^{i}y^{j} \in \mathbb Z[x,y]$ with $a\_{i},a\_{ij} \in [0,p-1]$ for some prime $p$. Let $F(q) = f\_{q}$, $G(q,r) = g\_{qr}$ for distinct primes $q,r \ge p $.

$a\_{i}$ can be got from $f\_{q}$ by mod $q$, subtraction, divide by $q$ operations. But the technique will fail for $g\_{qr}$.

$q=5$, $r=7$, $p=3$. $G\_{1}(x,y)=xy$, $G\_{2}(x,y)=x^{2} + 2x$. $G\_{1}(q,r) = 35 = G\_{2}(q,r)$ - [Wadim Zudilin](https://mathoverflow.net/users/4953/wadim-zudilin).

Can knowing $G(x,y)$ at more pairs $(q\_{k},r\_{k})\\_{k=1}^{m}$ where $p^{n\_{y}} > q\_{k} > p$ and $p^{n\_{x}} > r\_{k} > p$ help? - [Gerhard Paseman](https://mathoverflow.net/users/3455/gerhard-paseman1.).

$(1)$What is the minimum such $m$? Does $m$ depend on $n\_{x}$ and $n\_{y}$?

$(2)$What is the algorithm to extract $a\_{ij}$?

For $H(x\_{1},\cdots,x\_{t}) \in \mathbb Z[x\_{1},\cdots,x\_{t}]$,

$(A)$What is $m\_{t,n\_{x\_{i}}}$ - the minimum number of tuples, one should evaluate $H(x\_{1},\cdots,x\_{t})$?

$(B)$What is the algorithm to extract the coefficients?

$(C)$Is the growth in $m\_{t,n\_{x\_{i}}}$ logarithmic or linear or polynomial with respect to $t$ and $n\_{x\_{i}}$?

$\underline{Note}$: $m=1$ is trivially possible if one of $r$( or $q$) is greater than $p^{n\_{x}}$( or $p^{n\_{y}}$) and the other less than $p^{n\_{y}}$( or $p^{n\_{x}}$) but both greater than $p$.

I am facing a major hurdle in a critical step in matrix multiplication. If I can control the prime size to be of similar size, if $m$ is independent of $n$ or behaves logarithmically or linearly with $n$, and if I can extract the coefficients using mod operations quickly, then I have a chance of showing matrix multiplication is in $O(n^{2+\epsilon})$ complexity. My hurdle is in the bivariate case ($t=2$). I posted the generalization for arbitrary $t$ as well as the problem generalized.

<https://mathoverflow.net/questions/42846/shorter-version-of-computational-number-theory-problem>

**Tags:** cc.complexity-theory, nt.number-theory, algebraic-complexity

> **Comments:**
> **username_1**: apart from the formatting nightmare this question is, it sounds like this is a cross post from MO. please add in the link to the original post.  
> **username_2**: Motivation would help. Tell us why we should care.  
> **username_0**: added the motivation in the end.  
> **username_3**: Please stop asking one question at more than one place at the same time.  http://mathoverflow.net/questions/42740/computational-number-theory-problem  
> **username_4**: @Tsuyoshi: I'm not sure why this is an issue in general, as long as the cross-posting is transparent.  
> **username_3**: @username_4: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231  
> **username_0**: ok thank you Tsuyoshi  
> **username_0**: How do I close this?  

---

## 0 answers

