Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Helper code for ternary quadratic forms """
#***************************************************************************** # Copyright (C) 2012 Gustavo Rama # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import
from sage.rings.integer_ring import ZZ from sage.matrix.constructor import matrix, identity_matrix, diagonal_matrix from sage.modules.free_module_element import vector from sage.arith.all import inverse_mod, xgcd, gcd from sage.quadratic_forms.extras import extend_to_primitive from sage.rings.finite_rings.integer_mod import mod from sage.misc.prandom import randint from sage.functions.other import ceil, floor
def red_mfact(a,b): """ Auxiliary function for reduction that finds the reduction factor of a, b integers.
INPUT:
- a, b integers
OUTPUT:
Integer
EXAMPLES::
sage: from sage.quadratic_forms.ternary import red_mfact sage: red_mfact(0, 3) 0 sage: red_mfact(-5, 100) 9
"""
else:
def _reduced_ternary_form_eisenstein_with_matrix(a1, a2, a3, a23, a13, a12): """ Find the coefficients of the equivalent unique reduced ternary form according to the conditions of Dickson's "Studies in the Theory of Numbers", pp164-171, and the transformation matrix. See TernaryQF.is_eisenstein_reduced for the conditions.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _reduced_ternary_form_eisenstein_with_matrix sage: Q = TernaryQF([293, 315, 756, 908, 929, 522]) sage: qr, M = _reduced_ternary_form_eisenstein_with_matrix(293, 315, 756, 908, 929, 522) sage: qr (1, 2, 2, -1, 0, -1) sage: M [ -54 137 -38] [ -23 58 -16] [ 47 -119 33] sage: Qr = TernaryQF(qr) sage: Qr.is_eisenstein_reduced() True sage: Q(M) == Qr True
"""
# adjust
# cuadred 12
# cuadred 23
# cuadred 13
# order 12
# order 23
# order 12
# signs # a23, a13, a12 positive
else: # a23, a13, a12 nonpositive
if (a23==0): s1=1 else: if (a13==0): s2=1 else: if (a12==0): s3=1
################ ################
# adj 3 M*=matrix(ZZ,3,[-1,0,1,0,-1,1,0,0,1]) # a3 += a1+a2+a23+a13+a12 a23=-2*a2-a23-a12 a13=-2*a1-a13-a12
# adj 5.12 M*=matrix(ZZ,3,[-1,-1,0,0,-1,0,0,0,1]) #a2 += a1+a12 a23=-a23-a13 a13=-a13 a12=-a12 # = 2*a1+a12
# adj 5.13 M*=matrix(ZZ,3,[-1,0,-1,0,1,0,0,0,-1]) # a3 += a1+a13 a23=-a23-a12 a13=-a13 # = 2*a1+a13 a12=-a12
# adj 5.23 M*=matrix(ZZ,3,[1,0,0,0,-1,-1,0,0,-1]) # a3 += a2+a23 a23=-a23 # = 2*a2+a23 a13=-a13-a12 a12=-a12
# adj 4.12 M*=matrix(ZZ,3,[-1,-1,0,0,1,0,0,0,-1]) # a 2 += a1-a12 a23 = -a23 + a13 # a12 = 2*a1 - a12
# adj 4.13 M*=matrix(ZZ,3,[-1,0,-1,0,-1,0,0,0,1]) # a3 += a1-a13 a23 = -a23 + a12 # a13 = 2*a1 - a13
# adj 4.23 M*=matrix(ZZ,3,[-1,0,0,0,-1,-1,0,0,1]) # a3 += a2-a23 # a23 = 2*a2 - a23 a13 = -a13 + a12
# order 12 M*=matrix(ZZ,3,[0,-1,0,-1,0,0,0,0,-1]) [a1,a2]=[a2,a1] [a13,a23]=[a23,a13]
# order 23 M*=matrix(ZZ,3,[-1,0,0,0,0,-1,0,-1,0]) [a13,a12]=[a12,a13]
# order 12 M*=matrix(ZZ,3,[0,-1,0,-1,0,0,0,0,-1]) [a13,a23]=[a23,a13]
def _reduced_ternary_form_eisenstein_without_matrix(a1, a2, a3, a23, a13, a12): """ Find the coefficients of the equivalent unique reduced ternary form according to the conditions of Dickson's "Studies in the Theory of Numbers", pp164-171. See TernaryQF.is_eisenstein_reduced for the conditions.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _reduced_ternary_form_eisenstein_without_matrix sage: Q = TernaryQF([293, 315, 756, 908, 929, 522]) sage: qr = _reduced_ternary_form_eisenstein_without_matrix(293, 315, 756, 908, 929, 522) sage: qr (1, 2, 2, -1, 0, -1) sage: Qr = TernaryQF(qr) sage: Qr.is_eisenstein_reduced() True
"""
# adjust
# cuadred 12
# cuadred 23
# cuadred 13
# order 12
# order 23
# order 12
# signs # a23, a13, a12 positive
else: # a23, a13, a12 nonpositive
else: else:
################ ################
# adj 3 # a3 += a1+a2+a23+a13+a12 a23=-2*a2-a23-a12 a13=-2*a1-a13-a12
# adj 5.12 #a2 += a1+a12 a23=-a23-a13 a13=-a13 a12=-a12 # = 2*a1+a12
# adj 5.13 # a3 += a1+a13
# adj 5.23 # a3 += a2+a23 a23=-a23 # = 2*a2+a23 a13=-a13-a12 a12=-a12
# adj 4.12 # a 2 += a1-a12 a23 = -a23 + a13 # a12 = 2*a1 - a12
# adj 4.13 # a3 += a1-a13 a23 = -a23 + a12 # a13 = 2*a1 - a13
# adj 4.23 # a3 += a2-a23 # a23 = 2*a2 - a23 a13 = -a13 + a12
# order 12 [a1,a2]=[a2,a1] [a13,a23]=[a23,a13]
# order 23 [a13,a12]=[a12,a13]
# order 12 [a13,a23]=[a23,a13]
def primitivize(long long v0, long long v1, long long v2, p): """ Given a 3-tuple v not singular mod p, it returns a primitive 3-tuple version of v mod p.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import primitivize sage: primitivize(12, 13, 14, 5) (3, 2, 1) sage: primitivize(12, 13, 15, 5) (4, 1, 0)
"""
else: return 1, 0, 0
def evaluate(a, b, c, r, s, t, v): """ Function to evaluate the ternary quadratic form (a, b, c, r, s, t) in a 3-tuple v.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import evaluate sage: Q = TernaryQF([1, 2, 3, -1, 0, 0]) sage: v = (1, -1, 19) sage: Q(v) 1105 sage: evaluate(1, 2, 3, -1, 0, 0, v) 1105
"""
def _find_zeros_mod_p_2(a, b, c, r, s, t): """ Function to find the zeros mod 2 of a ternary quadratic form.
EXAMPLES::
sage: Q = TernaryQF([1, 2, 2, -1, 0, 0]) sage: from sage.quadratic_forms.ternary import _find_zeros_mod_p_2 sage: zeros = _find_zeros_mod_p_2(1, 2, 2, -1, 0, 0) sage: zeros [(0, 1, 0), (0, 0, 1), (1, 1, 1)] sage: Q((0, 1, 0)) 2 sage: Q((0, 0, 1)) 2 sage: Q((1, 1, 1)) 4
"""
def pseudorandom_primitive_zero_mod_p(a, b, c, r, s, t, p): """ Find a zero of the form (a, b, 1) of the ternary quadratic form given by the coefficients (a, b, c, r, s, t) mod p, where p is a odd prime that doesn't divide the discriminant.
EXAMPLES::
sage: Q = TernaryQF([1, 2, 2, -1, 0, 0]) sage: p = 1009 sage: from sage.quadratic_forms.ternary import pseudorandom_primitive_zero_mod_p sage: v = pseudorandom_primitive_zero_mod_p(1, 2, 2, -1, 0, 0, p) sage: v[2] 1 sage: Q(v)%p 0
"""
#[a,b,c,r,s,t] = Q.coefficients()
#return vector((z,r1*z+r2,1))%p
def _find_zeros_mod_p_odd(long long a, long long b, long long c, long long r, long long s, long long t, long long p, v): """ Find the zeros mod p, where p is an odd prime, of a ternary quadratic form given by its coefficients and a given zero of the form v.
The prime p does not divide the discriminant of the form.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _find_zeros_mod_p_odd sage: Q = TernaryQF([1, 2, 2, -1, 0, 0]) sage: p = 1009 sage: v = (817, 974, 1) sage: Q(v)%1009 0 sage: zeros_1009 = _find_zeros_mod_p_odd(1, 2, 2, -1, 0, 0, 1009, v) sage: len(zeros_1009) 1010 sage: zeros_1009.sort() sage: zeros_1009[0] (0, 32, 1) sage: Q((0, 32, 1)) 2018
"""
cdef long long a_i cdef long long c_i cdef long long a_inf cdef long long c_inf cdef long long i cdef long long l cdef long long x0 cdef long long y0
#b_i=(-2*b*i**2+2*b*i*y0+t*i*x0+2*a*x0-2*t*i+t*y0+r*i-2*a+s)%p more=True else: else: else: #b_inf=(2*b*y0+t*x0-2*b+r)%p else:
def _find_zeros_mod_p(a, b, c, r, s, t, p): """ Find the zeros mod `p` of the ternary quadratic form.
The quadratic form is given by the coefficients (a, b, c, r, s, t), and `p` is a prime that does not divide the discriminant of the form.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _find_zeros_mod_p sage: Q = TernaryQF([1, 2, 2, -1, 0, 0]) sage: p = 1009 sage: zeros_1009 = _find_zeros_mod_p(1, 2, 2, -1, 0, 0, p) sage: len(zeros_1009) 1010 sage: zeros_1009.sort() sage: zeros_1009[0] (0, 32, 1) sage: Q((0, 32, 1)) 2018 sage: zeros_2 = _find_zeros_mod_p(1, 2, 2, -1, 0, 0, 2) sage: zeros_2 [(0, 1, 0), (0, 0, 1), (1, 1, 1)]
"""
else:
def _find_all_ternary_qf_by_level_disc(long long N, long long d): """ Find the coefficients of all the reduced ternary quadratic forms given its discriminant d and level N. If N|4d and d|N^2, then it may be some forms with that discriminant and level.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _find_all_ternary_qf_by_level_disc sage: _find_all_ternary_qf_by_level_disc(44, 11) [(1, 1, 3, 0, -1, 0), (1, 1, 4, 1, 1, 1)] sage: _find_all_ternary_qf_by_level_disc(44, 11^2 * 16) [(3, 15, 15, -14, -2, -2), (4, 11, 12, 0, -4, 0)] sage: Q = TernaryQF([1, 1, 3, 0, -1, 0]) sage: Q.is_eisenstein_reduced() True sage: Q.reciprocal_reduced() Ternary quadratic form with integer coefficients: [4 11 12] [0 -4 0] sage: _find_all_ternary_qf_by_level_disc(44, 22) [] sage: _find_all_ternary_qf_by_level_disc(44, 33) Traceback (most recent call last): ... ValueError: There are no ternary forms of this level and discriminant
"""
cdef long long a cdef long long b cdef long long c cdef long long r cdef long long s cdef long long t cdef long long m cdef long long mu cdef long long g cdef long long u cdef long long v cdef long long g1 cdef long long m_q cdef double a_max cdef double r_max cdef double b_max cdef long long stu2 cdef long long mg
raise ValueError("There are no ternary forms of this level and discriminant") else:
else:
else:
is_reduced = False is_reduced = False is_reduced = False else: is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False
def _find_a_ternary_qf_by_level_disc(long long N, long long d): """ Find the coefficients of a reduced ternary quadratic form given its discriminant d and level N. If N|4d and d|N^2, then it may be a form with that discriminant and level.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _find_a_ternary_qf_by_level_disc sage: _find_a_ternary_qf_by_level_disc(44, 11) (1, 1, 3, 0, -1, 0) sage: _find_a_ternary_qf_by_level_disc(44, 11^2 * 16) (3, 15, 15, -14, -2, -2) sage: Q = TernaryQF([1, 1, 3, 0, -1, 0]) sage: Q.is_eisenstein_reduced() True sage: Q.level() 44 sage: Q.disc() 11 sage: _find_a_ternary_qf_by_level_disc(44, 22) sage: _find_a_ternary_qf_by_level_disc(44, 33) Traceback (most recent call last): ... ValueError: There are no ternary forms of this level and discriminant
"""
cdef long long a cdef long long b cdef long long c cdef long long r cdef long long s cdef long long t cdef long long m cdef long long mu cdef long long g cdef long long u cdef long long v cdef long long g1 cdef long long m_q cdef double a_max cdef double r_max cdef double b_max cdef long long stu2 cdef long long mg
raise ValueError("There are no ternary forms of this level and discriminant") else:
else:
else:
is_reduced = False is_reduced = False is_reduced = False is_reduced = False else: is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False is_reduced = False return ZZ(a), ZZ(b), ZZ(c), ZZ(r), ZZ(s), ZZ(t)
def extend(v): """ Return the coefficients of a matrix M such that M has determinant gcd(v) and the first column is v.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import extend sage: v = (6, 4, 12) sage: m = extend(v) sage: M = matrix(3, m) sage: M [ 6 1 0] [ 4 1 0] [12 0 1] sage: M.det() 2 sage: v = (-12, 20, 30) sage: m = extend(v) sage: M = matrix(3, m) sage: M [-12 1 0] [ 20 -2 1] [ 30 0 -7] sage: M.det() 2
"""
def _find_p_neighbor_from_vec(a, b, c, r, s, t, p, v, mat = False): """ Finds the coefficients of the reduced equivalent of the p-neighbor of the ternary quadratic given by Q = (a, b, c, r, s, t) form associated to a given vector v satisfying:
1. Q(v) = 0 mod p
2. v is a non-singular point of the conic Q(v) = 0 mod p.
Reference: Gonzalo Tornaria's Thesis, Thrm 3.5, p34.
EXAMPLES:
sage: from sage.quadratic_forms.ternary import _find_p_neighbor_from_vec sage: Q = TernaryQF([1, 3, 3, -2, 0, -1]) sage: Q Ternary quadratic form with integer coefficients: [1 3 3] [-2 0 -1] sage: Q.disc() 29 sage: v = (9, 7, 1) sage: v in Q.find_zeros_mod_p(11) True sage: q11, M = _find_p_neighbor_from_vec(1, 3, 3, -2, 0, -1, 11, v, mat = True) sage: Q11 = TernaryQF(q11) sage: Q11 Ternary quadratic form with integer coefficients: [1 2 4] [-1 -1 0] sage: M = matrix(3, M) sage: M [ -1 -5/11 7/11] [ 0 -10/11 3/11] [ 0 -3/11 13/11] sage: Q(M) == Q11 True
"""
else:
q, Mr = _reduced_ternary_form_eisenstein_with_matrix(ZZ(b00/2), ZZ(b11/2), ZZ(b22/2), ZZ(b12), ZZ(b02), ZZ(b01)) r00, r01, r02, r10, r11, r12, r20, r21, r22 = Mr.list() t00 = p*r20*w0 + (m0*w0/p + v0/p)*r00 + (m1*w0 + u0)*r10 t01 = p*r21*w0 + (m0*w0/p + v0/p)*r01 + (m1*w0 + u0)*r11 t02 = p*r22*w0 + (m0*w0/p + v0/p)*r02 + (m1*w0 + u0)*r12 t10 = p*r20*w1 + (m0*w1/p + v1/p)*r00 + (m1*w1 + u1)*r10 t11 = p*r21*w1 + (m0*w1/p + v1/p)*r01 + (m1*w1 + u1)*r11 t12 = p*r22*w1 + (m0*w1/p + v1/p)*r02 + (m1*w1 + u1)*r12 t20 = p*r20*w2 + (m0*w2/p + v2/p)*r00 + (m1*w2 + u2)*r10 t21 = p*r21*w2 + (m0*w2/p + v2/p)*r01 + (m1*w2 + u2)*r11 t22 = p*r22*w2 + (m0*w2/p + v2/p)*r02 + (m1*w2 + u2)*r12 return q, (t00, t01, t02, t10, t11, t12, t20, t21, t22) else:
def _basic_lemma_vec(a, b, c, r, s, t, n): """ Find a vector v such that the ternary quadratic form given by (a, b, c, r, s, t) evaluated at v is coprime with n a prime or 1.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _basic_lemma_vec sage: Q = TernaryQF([5, 2, 3, -1, 0, 0]) sage: v = _basic_lemma_vec(5, 2, 3, -1, 0, 0, 5) sage: v (0, 1, 0) sage: Q(v) 2
"""
return 0, 0, 0
return 1, 0, 0 elif c%n != 0: return 0, 0, 1
if r%n != 0: return 0, 1, 1 elif s%n != 0: return 1, 0, 1 elif t%n != 0: return 1, 1, 0
raise ValueError("not primitive form")
def _basic_lemma(a, b, c, r, s, t, n): """ Finds a number represented by the ternary quadratic form given by the coefficients (a, b, c, r, s, t) and coprime to the prime n.
EXAMPLES::
sage: from sage.quadratic_forms.ternary import _basic_lemma sage: Q = TernaryQF([5, 2, 3, -1, 0, 0]) sage: _basic_lemma(5, 2, 3, -1, 0, 0, 5) 2
"""
return 0
elif s%n != 0: return a + c + s elif t%n != 0: return a + b + t
raise ValueError("not primitive form") |