User azazello - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T08:17:20Z http://mathoverflow.net/feeds/user/27042 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114596/number-of-solutions-of-an-equation-over-finite-fields Number of solutions of an equation over finite fields azazello 2012-11-26T22:33:38Z 2012-11-30T18:08:22Z <p>Does anyone know of any result that deals with the following problem of counting the number of solutions of a certain algebraic equation over a finite field?</p> <p>Let $p$ be an odd prime and $(a,b,c,d)\in\mathbb{F}_p^4$. How many solutions does the following equation have:</p> <p>$$ab^2 + cd^2 = bc^2 + da^2.$$</p> <p>And more generally, if $1\le m,n\le q-1$ are two integers, how many solutions does the equation $$a^mb^n + c^md^n = b^mc^n + d^ma^n$$ have?</p> http://mathoverflow.net/questions/108976/what-graph-invariants-are-fast-to-compute What graph invariants are fast to compute? azazello 2012-10-06T03:26:12Z 2012-10-07T00:45:34Z <p>Problem: describe classes of automorphism for the following collection of graphs.</p> <p>Let $\mathbb{F}$ be a finite field of order $q$; then the vertex set V is defined as $V = {(x,y) : x\in\mathbb{F},y\in\mathbb{F}}$; adjacency is defined as follows: there is an arc from $(x_1,x_2)$ to $(y_1,y_2)$ iff $x_2 + y_2 = x_1^m y_1^n$, where $1\le m,n\le q-1$.</p> <p>Clearly, $|V|=q^2$, and the number of arcs is about $q^3$. Even for $q=17$ the problem of sorting all $(q-1)^2$ graphs corresponding to possible values of $m$ and $n$ becomes computationally hard. I've managed to obtain explicit formulas for the number of 2- and 3-cycles. So I first sort these graphs out by these parameters: this is done immediately. Then, by their diameter, then by their characteristic polynomial, then by the number of 4-cycles (this is done by brute-force). Only after that I'm checking them directly for isomorphism.</p> <p>Are there any other invariants that are easy to compute, so that I could separate the $(q-1)^2$ as close to isomorphic classes as possible before actually starting to check them for isomorphism directly. Would the Laplacian spectrum or something like this be "cheap" to compute?</p> http://mathoverflow.net/questions/114596/number-of-solutions-of-an-equation-over-finite-fields/114613#114613 Comment by azazello azazello 2012-11-27T03:23:16Z 2012-11-27T03:23:16Z Can any of you point to an elementary source where this is described. I have zero exposure to algebraic geometry. http://mathoverflow.net/questions/108976/what-graph-invariants-are-fast-to-compute/109011#109011 Comment by azazello azazello 2012-10-06T23:02:33Z 2012-10-06T23:02:33Z I meant $(m,n) = (1,3)$ and $(m,n) = (3,1)$. No, as I said counting 4-cycles after char poly's does refine subcollections of possibly isomorphic graphs. For a long time I had a conjecture that $G(q,m,n)$ and $G(q,n,m)$ are always isomorphic (well, at least they have the same number number of $k$-cycles for any natural $k$). But that turns out to be false. Other than that I can't say much. http://mathoverflow.net/questions/108976/what-graph-invariants-are-fast-to-compute Comment by azazello azazello 2012-10-06T06:05:55Z 2012-10-06T06:05:55Z Clear. Thank you. Also it appears that if any two such graphs (not necessarily isomorphic) have equal number of 4-cycles, then the numbers of 5- and 6-cycles are also equal.