login
Kronecker's triangle read by rows. T(n, k) = K(n, k) where K(n, k) is the Kronecker symbol (n / k).
25

%I #44 Jul 05 2024 07:04:54

%S 0,1,1,0,1,0,0,1,-1,0,0,1,0,1,0,0,1,-1,-1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,

%T -1,1,0,0,1,0,-1,0,-1,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,1,0,0,0,-1,0,1,

%U 0,0,1,-1,-1,1,1,1,1,-1,1,-1,0,0,1,0,0,0,-1,0,-1,0,0,0,1,0

%N Kronecker's triangle read by rows. T(n, k) = K(n, k) where K(n, k) is the Kronecker symbol (n / k).

%C Kronecker's triangle is a signed version of Euclid's triangle A217831 and generalizes and incorporates the Legendre and Jacobi symbols. However, the definition domain of the latter two symbols is inconsistently defined, so the Legendre symbol is typically only defined if the second argument is an odd prime or at least a positive odd integer. All such restrictions do not apply here (apart from limiting the range to the triangular domain 0 <= k <= n).

%C A096398 lists the indices of the rows that are identical in both triangles (i.e., Kronecker's and Euclid's). These are exactly the rows of T without negative terms.

%D Henri Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993, p. 28.

%H Jean-Paul Allouche, Leo Goldmakher, <a href="http://arxiv.org/abs/1608.03957">Mock characters and the Kronecker symbol</a>, arXiv:1608.03957 [math.NT], 2016.

%H Diego F. Aranha, B. S. Hvass, Bas Spitters and Mehdi Tibouchi, <a href="https://eprint.iacr.org/2023/1261.pdf">Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing</a>, ACM SIGSAC, Nov. 2023, p. 3228-3238.

%H Pierre Cartier, <a href="https://doi.org/10.5169/seals-43850">Sur une généralisation des symboles de Legendre-Jacobi</a>, Enseign. Math. (2), 16 (1970), 31-48.

%H Leopold Kronecker, <a href="https://archive.org/details/sitzungsberichte1885deutsch/page/761/mode/1up?view=theater">Zur Theorie der elliptischen Functionen</a>, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin, Jahrgang 1885, S. 770

%e Triangle K(n, k) starts:

%e [0] 0;

%e [1] 1, 1;

%e [2] 0, 1, 0;

%e [3] 0, 1, -1, 0;

%e [4] 0, 1, 0, 1, 0;

%e [5] 0, 1, -1, -1, 1, 0;

%e [6] 0, 1, 0, 0, 0, 1, 0;

%e [7] 0, 1, 1, 1, 1, -1, 1, 0;

%e [8] 0, 1, 0, -1, 0, -1, 0, 1, 0;

%e [9] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0;

%e .

%e Not limiting the range of k leads to the square array:

%e [0] 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ... A063524

%e [1] 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012

%e [2] 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, ... A091337

%e [3] 0, 1, -1, 0, 1, -1, 0, -1, -1, 0, ... A091338

%e [4] 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ... A000035

%e [5] 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, ... A080891

%e [6] 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, ... A322796

%e [7] 0, 1, 1, 1, 1, -1, 1, 0, 1, 1, ...

%e [8] 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, ...

%e [9] 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...

%e ...

%p K := (n, k) -> NumberTheory:-KroneckerSymbol(n, k):

%p seq(seq(K(n, k), k = 0..n), n = 0..12);

%t Table[KroneckerSymbol[n, k], {n, 0, 12}, {k, 0, n}] // Flatten

%o (Python) # Demonstrates how the Kronecker symbol

%o # can be layered on the Jacobi symbol.

%o from sympy import igcd

%o from sympy.ntheory import jacobi_symbol

%o # Alternatively, you can use the function JacobiSymbol from A372877.

%o def is_even(n): return n % 2 == 0

%o def kronecker_symbol(n, k):

%o if not (igcd(n, k) == 1): return 0

%o if n == 1 or k == 1: return 1

%o if is_even(k):

%o if is_even(n): return 0

%o s = 1 if is_even((n + 1) // 4) else -1

%o if k == 2: return s

%o return s * kronecker_symbol(n, k // 2)

%o return jacobi_symbol(n, k)

%o for n in range(20):

%o print([kronecker_symbol(n, k) for k in range(n + 1)])

%Y Family: A217831 (Euclid's triangle), A372877 (Jacobi's triangle), A372726 (Legendre's triangle), A373223 (Gauss' triangle), A373751 (quadratic residue modulo prime(n)), A373748 (quadratic residue/nonresidue modulo n).

%Y Cf. A071961 (row sums), A000010 (row sum of absolute terms, for n >= 2), A063524 (column 0 and main diagonal).

%Y Cf. A020639 (The index of the first appearance of 0 in row n of the array.)

%Y Cf. A373180 (The index of the first appearance of 1 in row n of the array.)

%Y Cf. A373088 (The index of the first appearance of -1 in row n of the array.)

%Y Cf. A096396 (number of 1s in the triangle row n), A096397 (number of -1s in the triangle row n), A062830 (number of 0s in the triangle row n).

%Y Cf. A096398, A372519 (indices of the rows whose sum vanishes).

%Y Cf. A063524, A000012, A091337, A091338, A000035, A080891, A322796.

%K sign,tabl

%O 0

%A _Peter Luschny_, May 16 2024