User - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:42:18Z http://mathoverflow.net/feeds/user/16007 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72721/diophantine-approximation Diophantine approximation unknown (yahoo) 2011-08-11T22:04:14Z 2012-09-05T19:25:28Z <p>Say absolute values of $a,b,c$ is $O(log^{k}{n})$ for some positive constant $k$. Given positive integer $n$ that is reasonably large, we cannot always find integers $a,b,c$ such that $|a{b^{c}} - n|$ is very close to $n$ say within $O(log(n))$ since there are only $log^{O(k)}{n}$ such $a,b,c$ combinations(answer from Petrov). </p> <p>What is the lower bound on $n$ as a function of $k$ upto which I can find such $a,b,c$?</p> http://mathoverflow.net/questions/71614/a-geometric-topology-notion-of-typical-sequences-power-of-typical-sequences-in-m A geometric/topology notion of Typical Sequences? Power of typical sequences in multiuser channels? unknown (yahoo) 2011-07-29T20:17:16Z 2012-08-17T12:22:01Z <p>The idea of Typical sequences(http://en.wikipedia.org/wiki/Typical_set) is a crucial concept in Shannon's proof of the Noisy channel coding theorem. Unfortunately the notion is not sufficient to settle the capacity of transmission of non-communicating correlated sources over independent channels to a common noisy receiver? Even the problem of two-user interference channel capacity with uncorrelated sources is open. What makes it hard to apply typicality to these cases? </p> <p>Is it possible to associate a geometry/topology to easily visualize typical sequences(atleast when the alphabets are $1$-dimensional reals - more complicated cases include matrix or non-commutatitve alphabets such as in Multiple Input and Multiple Output systems)? Shannon's proof(http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf) is geometry-less and very abstract.</p> http://mathoverflow.net/questions/84720/multiobjective-semidefinite-programming Multiobjective semidefinite programming unknown (yahoo) 2012-01-02T03:58:14Z 2012-01-04T18:04:20Z <p>Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.</p> <p>There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is arbitrary.</p> <p>$B$ and $C$ are known.</p> <p>Let $\mathbf{1_{m}}$ be all $\mathcal{1}$ vector of size $\mathcal{1} \times m$, $\forall m \in \mathbb{N}$.</p> <p>Let $A$ be size $n \times 2^{g(n)}$ (with $i,j$th entry $a_{ij}$) that needs to be found on the conditions:</p> <p>$(0)$ $AB = C$ (linear condition).</p> <p>$(1)$ $\mathbf{1_{n}}AB\mathbf{1_{n^{2}}}' = n^{\frac{3}{2}}$ (linear condition).</p> <p>$(2)$ $\|A\|_{F}^{2}$, the Frobenius norm of $A$ is minimized (quadratic objective).</p> <p>$(3)$ $\|\mathbf{1_{n}}A\|_{2}^{2}$ is maximized (quadratic objective).</p> <p>$(4)$ $\forall i,j$, $a_{ij} \in \mathcal{S}$ where $S$ is either $[-\mathcal{1},\mathcal{1}]$ or $[\mathcal{0},\mathcal{1}]$ (Relaxing $S^{n \times 2^{g(n)}}$ to a sphere enclosing a cube <code>$\{-\mathcal{1},\mathcal{1}\}^{n \times 2^{g(n)}}$</code> or <code>$\{\mathcal{0},\mathcal{1}\}^{n \times 2^{g(n)}}$</code> for both interval definitions of $S$ provides quadratic constraint).</p> <p>Is there a way to get a good approximation (tight lower/upper bounds) of <code>$\|\mathbf{1_{n}}A_{abs}\|_{0}$</code>? for the Donoho $0$-norm <code>$\|\mathbf{1_{n}}A_{abs}\|_{0}$</code> where $A_{abs}$ is $A$ but with all entries replaced by their absolute values?</p> <p>Any reference for this problem would be of help?</p> http://mathoverflow.net/questions/82672/representing-vertices-of-a-cube-using-linear-combination-of-tensor-product-of-sma Representing vertices of a cube using linear combination of tensor product of smaller cubes unknown (yahoo) 2011-12-05T04:44:11Z 2011-12-31T23:02:40Z <p>Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$. </p> <p>Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)</p> <p>Let <code>$\{Q_{i}\}_{i=1}^{n^{2}}$</code> and <code>$\{P_{j}\}$$_{j=1}^{N}</code> be points over F[4] and F[2] \otimes F[2] respectively. </p> <p>Let Q, P and \Lambda be matrices of size n^{2} \times n^{4}, N \times n^{4} and n^{2} \times N respectively with entries from F[0].</p> <p>The rows of Q and P be the points <code>\{Q_{i}\}_{i=1}^{n^{2}}</code> and <code>\{P_{j}\}$$_{j=1}^{N}$</code> respectively.</p> <p>Let $Q$ be known ($P$ and $\Lambda$ are unknowns) in the following equation:</p> <p>$\Lambda P = Q$</p> <p>What is the minimal size of $N$ so that one can expect a compatible $\Lambda$ and $P$ for a generic $Q$? Are there good lower and upper bounds for $N$?</p> <p>What tools could be useful to study this problem?</p> <hr> <p>With respect to Yemon Choi's comment: Regarding algortihms, a naive algorithm would run in worst case $3^{2Nn^{2}}$ complexity since it has to iterate over all possible values of of $F[0]$ as candidate entries of $\Lambda$ and $P$ for each given $N$ to check if there is a compatible solution. Even for $n=3$, this is formidable. Is there a faster algorithm to decide existence of compatibility for a given $N$? Could the cube to sphere relaxation help reduce complexity while giving something satisfactory?</p> <p>Are there any textbooks or papers that handle something similar to this?</p> http://mathoverflow.net/questions/82540/composition-of-weighted-multiedge-digraphs Composition of weighted multiedge digraphs unknown (yahoo) 2011-12-03T07:45:11Z 2011-12-03T08:37:23Z <p>Consider $G$ and $H$, two weighted multiedge digraphs with edge weights $\{g_{i}\}$$<em>{i=1}^{|E</em>{G}|} and \{h_{j}\}$$<em>{j=1}^{|H</em>{G}|}$ </p> <p>respectively where $|E_{G}|$ and $|E_{H}|$ are total number of edges in graphs $G$ and $H$ respectively and $g_{i},h_{j} \in \mathbb{R}$.</p> <p>What is correct definition of a(n associative) composition of $G$ and $H$? Is there a definable notion of adjacency and biadjacency matrices in terms of the constituent multiedged weighted digraphs?</p> <p>Will the composition be associative if the weights have $\pm \infty$ and $0$s?</p> <p>Are there any definitions of compositions without the Lexicographic product?</p> http://mathoverflow.net/questions/82202/isomorphic-regular-graphs Isomorphic regular graphs unknown (yahoo) 2011-11-29T17:33:09Z 2011-12-01T05:16:04Z <p>How many non-isomorphic classes of regular graphs on $(2n+1)^{m}$ vertices with $m(2n+1)^{m}$ edges with vertex degree $2m$, where $n,m \in \mathbb{N}$ are there? Is there a classification known? Can there can be more than one such class (that is are they all isomorphic)?</p> <p>Is there an example of such non-isomorphic graphs if there are any?</p> http://mathoverflow.net/questions/81084/reference-for-complexity-of-primitive-polynomials Reference for complexity of primitive polynomials unknown (yahoo) 2011-11-16T16:38:34Z 2011-11-21T17:40:17Z <p>What is the fastest known way to check if a given polynomial of degree $n$ in $F_{2}[X]$ is primitive?</p> <p>In response to Greg Kuperberg's answer. If we known factorization of $2^{n} - 1$, then what is the complexity?</p> http://mathoverflow.net/questions/81269/maximal-length-vector-under-constraints Maximal length vector under constraints unknown (yahoo) 2011-11-18T17:40:43Z 2011-11-19T23:05:09Z <p>Consider a criculant symmetric $M$ an $n \times n$ matrix with $0$ and $1$ entries and $r$ entries of $1$ in each row with the diagonal values taken as $1$. I am looking for a $0-1$ vector $v$ with the largest hamming weight such that $\langle v , \frac{1}{r}Mv \rangle$ $=$ $\langle v , v \rangle$.</p> <p>I am also looking for the rate of growth in the hamming weight as $m \rightarrow \infty$, $\langle v , \frac{1}{r^{m}}M^{\otimes{m}}v \rangle$ $=$ $\langle v , v \rangle$. What are some good mathematical techniques/tools to study this kind of problems?</p> http://mathoverflow.net/questions/79366/evidence-for-integer-factorization-is-in-p Evidence for integer factorization is in $P$ unknown (yahoo) 2011-10-28T08:34:32Z 2011-10-28T14:15:01Z <p>Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter Sarnak's lectures where he mentions that he does <a href="http://www.austms.org.au/tiki-download_file.php?fileId=161" rel="nofollow">not believe factoring is not in $P$</a>.</p> <p>What evidence is there that integer factorization is in $P$ other than the fact that polynomial factorization is in $P$?</p> http://mathoverflow.net/questions/68824/maximal-disjoint-hyperplanes Maximal disjoint Hyperplanes unknown (yahoo) 2011-06-26T01:44:44Z 2011-09-25T02:03:00Z <p>Given a set of $n^{r}$ points $X_{r} = \{ x_{1}, \cdots, x_{n^{r}} \}$ occupying a codim $t^{r}$ subspace in $\mathbb{R}^{n^{r}}$. Let $M_{r}$ be the set of $t^{r}$-tuples of these points.. So $|M_{r}| = \frac{n^{r}!}{(n^{r}-t^{r})!t^{r}!}$. Each $m \in M_{r}$ lie in a dim $t^{r}-1$ hyperplane in $\mathbb{R}^{n^{r}-t^{r}}$. So $M_{r}$ can be thought of as a set of dim $t^{r}-1$ hyperplanes. Consider $M_{sub,r}$ a subset of $M_{r}$. What is the maximum number of hyperplanes in $M_{sub,r}$ such that their intersection is empty?</p> <p>In my case there is a particular tensor structure to $M_{sub,r}$. That is $M_{sub,r}$ is just the $r$-fold tensor product of $M_{sub,1}$ and $|M_{sub,1}| = n$. Also $X_{r}$ is $n$-fold tensor product of $X$.</p> <p>Are there any known results or techniques to study this type of problem?</p> http://mathoverflow.net/questions/75491/diagonalization-of-a-variant-of-a-block-z-circulant-using-fft-techniques Diagonalization of a variant of a block z-circulant using FFT techniques unknown (yahoo) 2011-09-15T07:16:38Z 2011-09-16T03:38:29Z <p>Say $\Gamma_{i}$ are diagonal matrices for $i=1$ to $n$.</p> <p>$\Gamma_{1} \mbox{ }q\Gamma_{2} \mbox{ }q\Gamma_{3} \cdots \mbox{ }q\Gamma_{n}$</p> <p>$\Gamma_{2} \mbox{ }\Gamma_{3} \mbox{ }q\Gamma_{4} \cdots \mbox{ }q\Gamma_{1}$</p> <p>$\Gamma_{3} \mbox{ }\Gamma_{4} \mbox{ }\Gamma_{5} \cdots \mbox{ }q\Gamma_{2}$</p> <p>$\vdots$</p> <p>$\Gamma_{n-1} \mbox{ }\Gamma_{n} \mbox{ }\Gamma_{1} \cdots \mbox{ }q\Gamma_{n-2}$</p> <p>$\Gamma_{n} \mbox{ }\Gamma_{1} \mbox{ }\Gamma_{2} \cdots \mbox{ }\Gamma_{n-1}$</p> <p>be the given matrix $M$ which is 'variant' block z-circulant with diagonal blocks $\Gamma_{i}$ with $q$ the value of $z^{n}$. </p> <p>This is 'variant' because in usual $z$-circulant matrix the $q$ are in the lower half and the block matrices form a circulant structure (unlike here where a reverse circulant structure is formed).</p> <p>My question: Is there a standard way to diagonalize the above matrix using simple FFT techniques?</p> <p>If the matrix were a true block z-circulant then there is a standard way using pure FFT techniques and pre and post multiplication by a diagonal matrix and its inverse.</p> http://mathoverflow.net/questions/75089/factoring-and-index-calculus-and-duality-between-dl-and-factoring-via-compuationa Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them unknown (yahoo) 2011-09-10T11:03:12Z 2011-09-11T07:45:41Z <p>If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the <a href="http://en.wikipedia.org/wiki/Index_calculus_algorithm" rel="nofollow">index calculus algorithm</a> used for Discrete Log calculation in any serious way?</p> <p><strong>Other connections</strong></p> <p>$1.)$ "Number field cryptography" Johannes Buchmann Tsuyoshi Takagi Ulrich Vollmer</p> <p>The above paper mentions Root Problem (RP) and Group Order Problem (GOP) is same as factoring discriminant. So factoring easy implies RP and GOP are easy.</p> <p>$2.)$ "A Signature Scheme Based on the Intractability of Computing Roots" Ingrid Biehl Johannes Buchmann Safuat Hamdy Andreas Meyer</p> <p>The above paper mentions if DL is easy, Group Order Problem (GOP) is easy which inturn would imply Root Problem (RP) would be easy. So DL is easy implies RP and GOP are easy.</p> <p>Though unrelated to index calculus directly, could any of these links be used to show index calculus for DL could be done faster than $O(\sqrt{P})$ if factorization is quick? </p> <p>There seems to be some kind of duality between DL and factoring since both lead to easy solutions for RP and GOP.</p> http://mathoverflow.net/questions/75093/genus-of-algebraic-curves-with-unknown-degree Genus of algebraic curves with unknown degree unknown (yahoo) 2011-09-10T12:23:36Z 2011-09-11T06:46:57Z <p>I am not sure if this is a valid question but posting any way:</p> <p>Say I am over $\mathbb{F}_{p}$ for a prime $p$.</p> <p>I have a curve of form $x^{2} = f(y)$ where $f(y)$ has an unknown form (and hence degree). How many points do I need to know on the curve to estimate the genus of the curve? </p> <p>$A.)$We also have the additional constraint that $f(y)$ has atmost $2k$ non-zero coeffients where $k$ is a constant. Assume that a bound to the degree is known.</p> <p>$B.)$Assume $2k &lt;&lt; y$-degree of the equation.</p> <p>$C.)$Assume the coeffients of the highest half of the terms are $+1$ and the lowest half of terms are $-1$. (Just an artificial example - but this tells that one possibly may be able to get the genus without getting the coefficients. For a concrete realization of the artificial example, look at error correction codes over $3$ alphabets $\{ \pm1, 0 \}$. The errors can be in only $2k$ coordinates and I also know the errors in the top half will be $+1$ and the lower half will have errors with $-1$).</p> <p>How many points do you need? If degree bound is $D$, then would $O(\log^{h(k)}{D})$ points suffice where $h(k)$ is independent of $D$ and of the curve and is fixed for a fixed $k$? </p> http://mathoverflow.net/questions/74108/a-matrix-equation A Matrix equation unknown (yahoo) 2011-08-31T00:06:26Z 2011-08-31T03:11:03Z <p>Let $A$ and $B$ be two $n \times n$ full-rank matrices.</p> <p>Let $XAY = B$ be the given equation where $X$ and $Y$ are unknown $n \times n$ matrices. We know that $Vec(B) = (Y^{T} \otimes X)Vec(A)$. Under what conditions can we determine $X$ and $Y$ and what would be the procedure to determine $X$ and $Y$?</p> <p>Not looking for the obvious solutions such as $Y^{-1}=A$ and $X=B$, $A$ is the eigenvalue (or some multiple of eigenvalue) diagonal matrix of $B$ where $X$ and $Y$ diagonalizes $B$ and $A$ and $B$ are similar to $X$ and $Y$. In general are there any other possible choices that $Y^{T} \otimes X$ can take? These may be the only choices for general $A$ and $B$. However, given $A$ and $B$ are some other structured matrices, has such an equation been studied before?</p> http://mathoverflow.net/questions/70406/bilinear-system-of-diophantine-equations Bilinear system of Diophantine Equations unknown (yahoo) 2011-07-15T07:06:53Z 2011-08-27T11:57:44Z <p>$\forall i,j \in$ $\{$$1, \cdots,n$$\},$ let $x_{i},y_{i}$ be unknowns and $n_{ij} \in \mathbb{Z}$ with $i \le j$ be the knowns.</p> <p>Consider the following $\frac{n(n+1)}{2}$ with $n > 2$ overdetermined bilinear equations:</p> <p>$\sum_{\substack{j=1,}{j \ne i}}^{n} x_{j}y_{j} = -n_{ii} + x_{i}y_{i} \in \mathbb{Z}$.</p> <p>$x_{i}y_{j} + x_{j}y_{i} = n_{ij} \in \mathbb{Z}$ when $i &lt; j$.</p> <p>When is the system solvable and when is it solvable over $\mathbb{Z}$?</p> http://mathoverflow.net/questions/72752/goldbach-waring-problem-bound-on-n-in-huas-theorem Goldbach-Waring problem - Bound on $N$ in Hua's theorem? unknown (yahoo) 2011-08-12T09:33:26Z 2011-08-12T13:13:44Z <p><a href="http://mathoverflow.net/questions/70308/current-status-of-waring-goldbach-problem" rel="nofollow">http://mathoverflow.net/questions/70308/current-status-of-waring-goldbach-problem</a></p> <p><a href="http://en.wikipedia.org/wiki/Waring%E2%80%93Goldbach_problem" rel="nofollow">http://en.wikipedia.org/wiki/Waring%E2%80%93Goldbach_problem</a></p> <p>Wiki says that WG conjecture is that for every $k$, $\exists$ primes $p_{1}, p_{2}, \cdots p_{t}$ where $t$ is independent of $k$ such that $\sum_{i=1}^{t}p_{i}^{k} = N$ for large enough $N$.</p> <p>Hua showed $t$ is atmost $O(k^{2}log{k})$. In his theorem, does anyone know the bounds on $N$ given $k$? Is it bounded below $O(2^{k})$ (that is for every $N > N_{0} = O(2^{k})$ does Hua's theorem hold)?</p> http://mathoverflow.net/questions/72665/sum-of-higher-powers-bound-on-n Sum of higher powers (bound on $N$) unknown (yahoo) 2011-08-11T08:23:19Z 2011-08-11T14:36:04Z <p><a href="http://mathoverflow.net/questions/437/sums-of-cubes-and-more" rel="nofollow">http://mathoverflow.net/questions/437/sums-of-cubes-and-more</a></p> <p>In the selected answer to the above question the writer states ""what is the least $G=G(k)$ such that for some $N$, every integer greater than $N$ can be represented as the sum of $G$ $k$-th powers"</p> <p>For $G(k)$ that we have explicit bounds in <a href="http://www.maths.bris.ac.uk/~matdw/2002%20wps.pdf" rel="nofollow">http://www.maths.bris.ac.uk/~matdw/2002%20wps.pdf</a>.</p> <p>Does anyone know any bounds for the values of $N$ for any $k$ would be?</p> http://mathoverflow.net/questions/72628/number-theory-and-np-complete Number theory and NP-complete unknown (yahoo) 2011-08-10T22:04:22Z 2011-08-11T05:38:36Z <p>What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.</p> http://mathoverflow.net/questions/71673/fourier-transform-in-mathematica/71675#71675 Answer by unknown (yahoo) for Fourier transform in Mathematica unknown (yahoo) 2011-07-30T18:45:56Z 2011-07-30T18:45:56Z <p>Normalizing factor.</p> <p>It looks like R defines the Discrete Fourier Transform matrix as $F = [1$ $1; 1$ $-1]$ while Mathematica defines it as $F = \frac{1}{\sqrt{2}}[1$ $1; 1$ $-1]$.</p> <p>If you do inverse fft - R would define it to be $F^{-1} = \frac{1}{2}[1$ $1; 1$ $-1]$ while Mathematica would define it as $F^{-1} = F^{H} = \frac{1}{\sqrt{2}}[1$ $1; 1$ $-1]$ where $H$ is Hermitian transpose.</p> http://mathoverflow.net/questions/71467/graph-laplacian-to-continuous-version Graph Laplacian to Continuous version unknown (yahoo) 2011-07-28T06:00:22Z 2011-07-28T06:00:22Z <p>Has there been a study of vector laplacian that is a continuous version of a graph laplacian? Is there a good introduction to the topic?</p> http://mathoverflow.net/questions/71108/sparse-eigenvectors-for-the-discrete-fourier-transform-matrix Sparse Eigenvectors for the Discrete Fourier Transform matrix unknown (yahoo) 2011-07-24T06:35:24Z 2011-07-24T19:23:28Z <p>There are many ways to choose eigenbasis for the Discrete Fourier Transform matrix since it has only $4$ distinct eigenvalues taken from $\{\pm 1,\pm i\}$.</p> <p>Has there been any refereed work that provides a sparse eigenvector basis for the Discrete Fourier Transform matrix?</p> http://mathoverflow.net/questions/52803/can-gauss-sums-derandomize-any-heuristic-arguments/71111#71111 Answer by unknown (yahoo) for Can Gauss sums derandomize any heuristic arguments? unknown (yahoo) 2011-07-24T08:07:00Z 2011-07-24T08:07:00Z <p>Actually I would think there are connections. Even if the the coincidence $\sqrt{p}$ seems ordinary, there are low-correlation sequences which owe their low correlation to Gauss sum estimates and looking from a probabilistic view point sequences, I would think there would be interpretations from a view point of uncorrelated random variables. Your starting point could be low-correlation sequences used in communications systems and beyond that I would think Nicholas Katz and Sarnak's dive into random matrices would help. <a href="http://books.google.com/books?id=wXyOPbzvowsC&amp;printsec=frontcover&amp;dq=inauthor:%22Nicholas+M.+Katz%22&amp;hl=en&amp;ei=j9IrTu24CpKnsAKG5c3DCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=5&amp;ved=0CD8Q6AEwBA#v=onepage&amp;q&amp;f=false" rel="nofollow">http://books.google.com/books?id=wXyOPbzvowsC&amp;printsec=frontcover&amp;dq=inauthor:%22Nicholas+M.+Katz%22&amp;hl=en&amp;ei=j9IrTu24CpKnsAKG5c3DCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=5&amp;ved=0CD8Q6AEwBA#v=onepage&amp;q&amp;f=false</a></p> http://mathoverflow.net/questions/70595/lee-codes-and-n-torus Lee codes and $n$-torus unknown (yahoo) 2011-07-18T07:06:56Z 2011-07-20T19:41:02Z <p>This is in continuation with this post: <a href="http://mathoverflow.net/questions/70524/geometric-analytic-techniques-for-constructive-and-asymptotic-bounds-in-the-lee-m" rel="nofollow">http://mathoverflow.net/questions/70524/geometric-analytic-techniques-for-constructive-and-asymptotic-bounds-in-the-lee-m</a></p> <p>Codes over alphabet $\mathbb{Z}_{q}$ of length $n$ for the Lee metric seems to be connected to spaced points on the $n$-torus since both seem to have some circular nature over each dimension. Are there any references which talks about their connection rigorously?</p> <p>From wiki:</p> <p>In coding theory, the "Lee distance" is a distance between two strings $x_{1} x_{2} \dots x_{n}$ and $y_{1} y_{2} \dots y_{n}$ of equal length $n$ over the $q$-ary alphabet $\{0,1,\cdots,q-1\}$ of size $q\ge2$. It is a metric, defined as</p> <p>$\sum_{i=1}^n \min(|x_i-y_i|,q-|x_i-y_i|)$</p> <p>If $q=2$ or $3$, the Lee distance coincides with the Hamming distance.</p> <p>The metric space induced by the Lee distance is a discrete analog of the Elliptic geometry|elliptic space.</p> http://mathoverflow.net/questions/70524/geometric-analytic-techniques-for-constructive-and-asymptotic-bounds-in-the-lee-m Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric unknown (yahoo) 2011-07-16T21:53:18Z 2011-07-17T01:17:17Z <p>Slight extension of cross posting from <a href="http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang" rel="nofollow">http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang</a> (closed there)</p> <p>The following link provides a Gilbert-Varshamov lower bound and a Hamming upper bound for the Lee metric when the distance between codewords is smaller than the length of the code (captured by $r = \delta n$ where $0 \le \delta \le 0.37$ in the paper).</p> <p><a href="ftp://ftp.cs.brown.edu/pub/techreports/91/cs91-29.pdf" rel="nofollow">ftp://ftp.cs.brown.edu/pub/techreports/91/cs91-29.pdf</a></p> <p>Consider the alphabet is of form $2k + 1$ where $k$ is any non-negative integer.</p> <p>Is there a reference which provides the corresponding lower/upper bound for ranges above this? Atleast is there a lower bound (preferably as powerful as the Gilbert-Varshamov bound) and a upper bound(preferably tighter than the Hamming bound) for the case $\frac{2 \delta n + 1}{n} = \frac{n + 1}{n}$, that is $\delta = \frac{1}{2}$?</p> <p>Are there any constructive techniques known for the case $\delta = 0.5$ for all/any even/any odd $n$ to build good codes?</p> <p>Are there any spectral/fourier analytic/algebraic geometric techniques that has studied this problem? In particular are there connections to domino tiling that are studied anywhere?</p> http://mathoverflow.net/questions/70471/is-there-a-name-for-these-sets-in-a-finite-field-ring Is there a name for these sets in a finite field/ring? unknown (yahoo) 2011-07-16T00:19:27Z 2011-07-16T00:26:06Z <p>Let $\mathbb{F}_{p^{mn}}$ be a Finite Field with Char $p$ with $\zeta$ a primitive element in the field.</p> <p>$\forall {k} \in $$\{$$1,\cdots,m$$\}, \forall {i}_{k} \in$$\{$$0,\cdots,p-1$$\}$, consider the two sets of $p^{m}$ elements of the form </p> <p>$(1)$$\displaystyle \sum_{j=1}^{n} \displaystyle \sum_{k=1}^{m}(ji_{k} \mod p)p^{k+m(j-1)-1} \in \mathbb{Z}_{p^{mn}}.</p> <p>(2)$$\displaystyle \sum_{j=1}^{n} \displaystyle \sum_{k=1}^{m}(ji_{k} \mod p)\zeta^{k+m(j-1)-1} \in \mathbb{F}_{p^{mn}}$.</p> <p>$(3)$$\zeta^{\displaystyle \sum_{j=1}^{n} \displaystyle \sum_{k=1}^{m}(ji_{k} \mod p)p^{k+m(j-1)-1}} \in \mathbb{F}_{p^{mn}}$ where the exponent is in $\mathbb{Z}$.</p> <p>Is there a name for these sets?</p> <p>When $p$ is not prime we will not be in a finite field, however is there a term for $(1)$ in this case and is there something analogous to $(2)$ and $(3)$ in this case?</p> http://mathoverflow.net/questions/70208/system-of-diophantine-equations System of Diophantine equations unknown (yahoo) 2011-07-13T10:25:25Z 2011-07-14T05:26:11Z <p>$p + p' = m$</p> <p>$q - q' = n$</p> <p>$pp' = qq'$</p> <p>$(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$.</p> <p>Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently?</p> http://mathoverflow.net/questions/69164/pdes-from-vector-fields-whose-inner-product-with-their-vector-laplacian-equals PDES - from Vector fields whose inner product with their vector Laplacian equals norm of the vector field unknown (yahoo) 2011-06-30T06:45:52Z 2011-06-30T20:33:12Z <p>Let $g(x_{1},........,x_{n}) = \sum_{i=1}^{n}g_{i}(x_{1},\cdots,x_{n})e_{i}$ be a function in $\mathbb{C}^n$ ($e_{i}$ are the standard bases).</p> <p>Let $\nabla^{2}$ be the vector Laplacian. Let $&lt;\cdot,\cdot>$ be inner product between two vectors.</p> <blockquote> <p><strong>Consider the PDE $&lt;{g},{\nabla^2(g)}> = &lt;{g},{g}>$.</strong></p> <p>$(A)$ <strong>What is such a class of equation formally called in the literature (it seems to be inner product of a field with its vector Laplacian)?</strong></p> <p>$(B)$ <strong>What are the solutions to the above pde?</strong></p> <p>$(C)$ <strong>What are the solutions of $g$ if $g_{i}(x_{1},\cdots,x_{n}) \in [0,1]$ $\forall i$?</strong></p> <p>$(D)$ <strong>What are the solutions for the special case $g_{i}(x_{1},\cdots,x_{n}) = g_{i}(x_{i})$?</strong></p> <p>$(E)$ <strong>What happens if I replace $\mathbb{C}^{n}$ by:</strong></p> <blockquote> <blockquote> <p>$(1)$ <strong>a torus $\mathbb{C}^{n}/L$ where $L$ is a lattice</strong></p> <p>$(2)$ <strong>a sphere centered at $(\frac{1}{2}, \frac{1}{2}, \cdots,\frac{1}{2})$ and radius $\frac{\sqrt{n}}{2}$.</strong></p> <p>$(3)$ <strong>a cube given by the $0-1$ combinations of the standard bases $e_{i}$ (or its closest smooth approximation) enclosing the above sphere.</strong></p> </blockquote> </blockquote> <p>$(F)$ <strong>Does anything interesting happen as limit $n\rightarrow\infty$.</strong></p> </blockquote> <p>I feel this is a standard pde. However, since I am not in the math field, I do not know the keywords or whether there are standard solutions? Where should I look for them? </p> http://mathoverflow.net/questions/85632/good-reference-for-representation-theory-of-non-commutative-finite-groups Comment by 2012-01-14T03:29:41Z 2012-01-14T03:29:41Z Hey Benjamin this is not a duplicate. Most books I have seen start with abelian examples and may only slightly cover non-commutative. Is their a good reference that focuses on non-commutative groups. http://mathoverflow.net/questions/82672/representing-vertices-of-a-cube-using-linear-combination-of-tensor-product-of-sma Comment by 2011-12-31T22:50:02Z 2011-12-31T22:50:02Z @Yemon Choi: I realized that I am only interested in the cube setting. FInite field setting seemed to be irrelevant. So I removed the finite field setting. http://mathoverflow.net/questions/82672/representing-vertices-of-a-cube-using-linear-combination-of-tensor-product-of-sma Comment by 2011-12-05T17:57:08Z 2011-12-05T17:57:08Z @Mark Sapir: Updated the question. I think it may make more sense now. http://mathoverflow.net/questions/82672/representing-vertices-of-a-cube-using-linear-combination-of-tensor-product-of-sma Comment by 2011-12-05T17:56:47Z 2011-12-05T17:56:47Z @Yemon Choi: Updated the question. http://mathoverflow.net/questions/82672/representing-vertices-of-a-cube-using-linear-combination-of-tensor-product-of-sma Comment by 2011-12-05T05:54:38Z 2011-12-05T05:54:38Z @Mark Sapir: Actually I was thinking of the former one, since I do not know how I would define a tensor product in the former one non-trivially (I may be wrong on this but I meant the former one). http://mathoverflow.net/questions/82202/isomorphic-regular-graphs Comment by 2011-11-29T17:52:52Z 2011-11-29T17:52:52Z @Chris this is not a hw. Corrected! http://mathoverflow.net/questions/57725/strassen-algorithm-7-multiplications/57740#57740 Comment by 2011-11-22T20:26:04Z 2011-11-22T20:26:04Z @Gerry: Thankyou:)!! http://mathoverflow.net/questions/57725/strassen-algorithm-7-multiplications/57740#57740 Comment by 2011-11-22T00:35:33Z 2011-11-22T00:35:33Z @Gerry Where is the reference for the information you have that it is atleast $19$? http://mathoverflow.net/questions/81269/maximal-length-vector-under-constraints/81383#81383 Comment by 2011-11-20T00:14:14Z 2011-11-20T00:14:14Z I will probably post another post! Thankyou! http://mathoverflow.net/questions/81269/maximal-length-vector-under-constraints/81383#81383 Comment by 2011-11-20T00:12:16Z 2011-11-20T00:12:16Z I think I am thinking something else. may be I need to rephrase a bit! http://mathoverflow.net/questions/81208/bounded-positive-integer-points-on-a-hyperplane Comment by 2011-11-18T03:15:58Z 2011-11-18T03:15:58Z @BR So is that count going to be $O(N^{a})$ or $O((\log{N})^{a})$? http://mathoverflow.net/questions/80165/a-quadratic-diophantine-problem Comment by 2011-11-06T03:14:44Z 2011-11-06T03:14:44Z only $N$ is given. http://mathoverflow.net/questions/80165/a-quadratic-diophantine-problem Comment by 2011-11-06T03:05:36Z 2011-11-06T03:05:36Z @Gerhard: I don't think the solution is that simple. When $n=c=0$, and $a,b$ in primes (including $1$) I doubt we can always get solutions. Although the cases where one can find will be interesting. When $c \ne 0$ and $N$ is composite, I think one should be able to find solutions with $a,b,c$ being primes (just guessing). When $N$ is prime, I doubt we will ever have $a,b$ and $c$ as primes. http://mathoverflow.net/questions/80165/a-quadratic-diophantine-problem Comment by 2011-11-06T02:05:18Z 2011-11-06T02:05:18Z thankyou:) I am still learning the notations:) http://mathoverflow.net/questions/76246/complexity-vs-length-of-a-proof Comment by 2011-09-25T01:30:36Z 2011-09-25T01:30:36Z Even Wiles tried different tricks with many examples until one worked (not much different from programming)!