ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 29 May 2013 16:11:40 +0200How to find instances where $d(a,b) = p^2$ for $p$ a primehttps://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for $p$ a prime? What are some techniques for accomplishing this? Should I first filter out a list of primes using `isprime` and then check possible pairs $(a,b)$ for each prime $p < N$, say $1000$.
Thu, 23 May 2013 14:12:39 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/Comment by DSM for <p>Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for $p$ a prime? What are some techniques for accomplishing this? Should I first filter out a list of primes using <code>isprime</code> and then check possible pairs $(a,b)$ for each prime $p < N$, say $1000$. </p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17651#post-id-17651Are you sure there are any such pairs to find? Unless I'm missing something, you can't fit $2p^2$ into $(a+1) (b+1) (a+b+2)$ successfully.Thu, 23 May 2013 14:56:36 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17651#post-id-17651Comment by JoshIzzard for <p>Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for $p$ a prime? What are some techniques for accomplishing this? Should I first filter out a list of primes using <code>isprime</code> and then check possible pairs $(a,b)$ for each prime $p < N$, say $1000$. </p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17650#post-id-17650Ah @DSM this may indeed be the case. Now I suppose I would like to find points where $d(a,b) = n$ for $n \in \mathbb{N}$. Does Sage have a toolkit that allows me to extract integral points on the surface $F(a,b,n) = d(a,b) - n = 0$?Thu, 23 May 2013 15:57:44 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17650#post-id-17650Answer by vdelecroix for <p>Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for $p$ a prime? What are some techniques for accomplishing this? Should I first filter out a list of primes using <code>isprime</code> and then check possible pairs $(a,b)$ for each prime $p < N$, say $1000$. </p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?answer=14969#post-id-14969Just to improve tmonteil answer you can use simple nested loops to enumerate solutions with the same "complexity" using the fact that your function d(a,b) is increasing in both variables:
N = 2*n
a = floor(sqrt(N-1))
b = 0
while a != -1:
while (a+1)*(b+1)*(a+b+2) < N:
b += 1
if (a+1)*(b+1)*(a+b+2) == N:
print a,b
else:
b -= 1
a -= 1
and then, computing the solution for N=2*3065451 runs in 8.33 ms which looks like a thousand times better !
And I am pretty sure that it is possible to do something more clever than increasing/decreasing by units in my function above...Fri, 24 May 2013 18:20:57 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?answer=14969#post-id-14969Comment by JoshIzzard for <p>Just to improve tmonteil answer you can use simple nested loops to enumerate solutions with the same "complexity" using the fact that your function d(a,b) is increasing in both variables:</p>
<pre><code>N = 2*n
a = floor(sqrt(N-1))
b = 0
while a != -1:
while (a+1)*(b+1)*(a+b+2) < N:
b += 1
if (a+1)*(b+1)*(a+b+2) == N:
print a,b
else:
b -= 1
a -= 1
</code></pre>
<p>and then, computing the solution for N=2*3065451 runs in 8.33 ms which looks like a thousand times better !</p>
<p>And I am pretty sure that it is possible to do something more clever than increasing/decreasing by units in my function above...</p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17620#post-id-17620@vdelecroix thanks very much, this is quite impressiveWed, 29 May 2013 15:58:53 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17620#post-id-17620Answer by tmonteil for <p>Suppose I have a dimension formula (for a Lie algebra representation) given by
$\mathrm{dim}_{a,b} = {(a+1)(b+1)(a+b+2) \over 2}$. I now would like to find pairs $(a,b)$ where $\dim_{a,b} = p^2$ for $p$ a prime? What are some techniques for accomplishing this? Should I first filter out a list of primes using <code>isprime</code> and then check possible pairs $(a,b)$ for each prime $p < N$, say $1000$. </p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?answer=14963#post-id-14963I am not sure i understand your question correctly. If you want to iterate over the pairs of integers, you can have a look at [multidimensional enumeration](http://www.sagemath.org/doc/reference/misc/sage/misc/mrange.html):
sage: f = lambda a,b : (a+1)*(b+1)*(a+b+2)
sage: n = 720
sage: for a,b in xmrange([n,n]):
sage: if f(a,b) == 2*n:
sage: print a,b
7 9
9 7
And actually you can be more restrictive and ask `a` and `b` to be less than `floor(sqrt(2*n))` (instead of `n`):
sage: bound = floor(sqrt(2*n))
sage: for a,b in xmrange([bound,bound]):
sage: if f(a,b) == 2*n:
sage: print a,b
7 9
9 7
Hence, you get all answers in time $O(n)$ instead of $O(n^2)$. But why not solving directly your equation ? Unfortunately, it seems that the solver is not able to solve the diophantine equation `f(a,b) == 2*n` directly:
sage: var('a','b')
(a, b)
sage: solve([f(a,b) == 2*n ], a, b)
([a == -1/2*(4*b + sqrt(b^4 + 4*b^3 + 6*b^2 + 5764*b + 5761) + b^2 + 3)/(b + 1), a == -1/2*(4*b - sqrt(b^4 + 4*b^3 + 6*b^2 + 5764*b + 5761) + b^2 + 3)/(b + 1)],
[1, 1])
But you can still use Sage solver when `a` is fixed:
sage: var('b')
b
sage: assume(b, 'integer')
sage: assume(b >= 0)
sage: for a in xrange(bound):
sage: sol = solve([f(a,b) == 2*n],b)
sage: if len(sol) != 0:
sage: print a, sol[0].rhs()
sage:
7 9
9 7
Now, you get an answer in time $O(\sqrt{n})$, which is not completely satisfactory (one could expect a polynomial in $\log(n)$), but not that bad.
That said, since the solver is quite slow, the multiplicative constant in the complexity is quite huge and the previous method is faster for small n (this is clear for `n=6216` : `42.7ms` vs `1.11s`). The last method becomes faster only later (this is clear for `n=3065451` : `94.43s` vs `29.77s`).
Thu, 23 May 2013 17:12:39 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?answer=14963#post-id-14963Comment by JoshIzzard for <p>I am not sure i understand your question correctly. If you want to iterate over the pairs of integers, you can have a look at <a href="http://www.sagemath.org/doc/reference/misc/sage/misc/mrange.html">multidimensional enumeration</a>:</p>
<pre><code>sage: f = lambda a,b : (a+1)*(b+1)*(a+b+2)
sage: n = 720
sage: for a,b in xmrange([n,n]):
sage: if f(a,b) == 2*n:
sage: print a,b
7 9
9 7
</code></pre>
<p>And actually you can be more restrictive and ask <code>a</code> and <code>b</code> to be less than <code>floor(sqrt(2*n))</code> (instead of <code>n</code>):</p>
<pre><code>sage: bound = floor(sqrt(2*n))
sage: for a,b in xmrange([bound,bound]):
sage: if f(a,b) == 2*n:
sage: print a,b
7 9
9 7
</code></pre>
<p>Hence, you get all answers in time $O(n)$ instead of $O(n^2)$. But why not solving directly your equation ? Unfortunately, it seems that the solver is not able to solve the diophantine equation <code>f(a,b) == 2*n</code> directly:</p>
<pre><code>sage: var('a','b')
(a, b)
sage: solve([f(a,b) == 2*n ], a, b)
([a == -1/2*(4*b + sqrt(b^4 + 4*b^3 + 6*b^2 + 5764*b + 5761) + b^2 + 3)/(b + 1), a == -1/2*(4*b - sqrt(b^4 + 4*b^3 + 6*b^2 + 5764*b + 5761) + b^2 + 3)/(b + 1)],
[1, 1])
</code></pre>
<p>But you can still use Sage solver when <code>a</code> is fixed:</p>
<pre><code>sage: var('b')
b
sage: assume(b, 'integer')
sage: assume(b >= 0)
sage: for a in xrange(bound):
sage: sol = solve([f(a,b) == 2*n],b)
sage: if len(sol) != 0:
sage: print a, sol[0].rhs()
sage:
7 9
9 7
</code></pre>
<p>Now, you get an answer in time $O(\sqrt{n})$, which is not completely satisfactory (one could expect a polynomial in $\log(n)$), but not that bad.</p>
<p>That said, since the solver is quite slow, the multiplicative constant in the complexity is quite huge and the previous method is faster for small n (this is clear for <code>n=6216</code> : <code>42.7ms</code> vs <code>1.11s</code>). The last method becomes faster only later (this is clear for <code>n=3065451</code> : <code>94.43s</code> vs <code>29.77s</code>).</p>
https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17619#post-id-17619@tmontneil Thank you for taking the time to write out this detailed solution. You have given me an idea as to how to move forward with this for more detailed dimension formulae. Eventually I hope to write an algorithm that checks for dimension equal to $p^2$ for the type $D_{2k+1}$ Lie algebras as well, but that dimension formula is quite a bit more complicated (if you are interested in the subject see Fulton and Harris p. 410 exercise 24.42). Thanks again for your help. RegardsWed, 29 May 2013 16:11:40 +0200https://ask.sagemath.org/question/10140/how-to-find-instances-where-dab-p2-for-p-a-prime/?comment=17619#post-id-17619