Primitive pythagorean codes

International Mathematical Forum, Vol. 8, 2013, no. 38, 1873 - 1879 HIKARI Ltd, www.m-hikari.com http://dx.doi.org/10.12988/imf.2013.39180 Primitive Pythagorean Codes Massond Malek California State University. East Bay Hayward. CA 94542, USA massoucl malek@csueastbay.edu Copyright @ 2013 Massoud Malek. This is an open access article distributed under the Creative Commons Attribution License. which permits unrestricted use. clisrriburion. and reproduction in any medium. provided the original work is properly cited. Abstract, In this paper, we shall define a simple generating matrix which produces all the primitive Pythagorean triples. ‘Then we define classes of codes with primitive Pythagorean triples. These classes are very simple to encode and decode messages. Ther also have a very good data compression quality. Keywords: Primitive Pythagorean triple; PPT: Pythagorean Triangle; Pythagoras, Plato. Euclid: generating matrix: Pythagercan alphabet: Coding theory: Cosct Leader decoding; aud Data Compression Introduction A Pythagorean triple, is a triple uf positive integers a,b, and € such that a right angle triangle exists with legs a. b and livpotenuse e. By the Pythagorean theorem, this is equivalent to finding positive integers a. band e. satisfving +) > a +b =e, If a aud 6 are relatively prime, then the Pythagorean Lriple is called primitive. The smallest. and best-known Pythagorean triple is (3, 4,5). The triangle generated by a Pythagorean triple is called a Pythagorean triangle. In all that follows we denote the primitive Pythagorean triple or triangle by PPT. Plaro (380 B.C.) is attributed with the formula: <l,n> = (ul 2n, u +1), A more general formula for obtaining all triples was given by Euclid in c. 300 B.C.

International Mathematical Forum, Vol. 8, 2013, no. 38, 1873 - 1879 HIKARI Ltd, www.m-hikari.com http://dx.doi.org/10.12988/imf.2013.39180 Primitive Pythagorean Codes Massoud Malek California State University, East Bay Hayward, CA 94542, USA massoud.malek@csueastbay.edu c 2013 Massoud Malek. This is an open access article distributed under the Creative Copyright  Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract In this paper, we shall define a simple generating matrix which produces all the primitive Pythagorean triples. Then we define classes of codes with primitive Pythagorean triples. These classes are very simple to encode and decode messages. They also have a very good data compression quality. Keywords: Primitive Pythagorean triple; PPT; Pythagorean Triangle; Pythagoras, Plato, Euclid; generating matrix; Pythagorean alphabet; Coding theory; Coset Leader decoding; and Data Compression Introduction A Pythagorean triple, is a triple of positive integers a , b, and c such that a right angle triangle exists with legs a , b and hypotenuse c . By the Pythagorean theorem, this is equivalent to finding positive integers a , b , and c , satisfying a2 + b2 = c2 . If a and b are relatively prime, then the Pythagorean triple is called primitive. The smallest and best-known Pythagorean triple is (3 , 4 , 5). The triangle generated by a Pythagorean triple is called a Pythagorean triangle. In all that follows we denote the primitive Pythagorean triple or triangle by PPT. Plato (380 B. C.) is attributed with the formula: < 1 , n > = (n2 − 1, 2 n, n2 + 1), A more general formula for obtaining all triples was given by Euclid in c. 300 B.C.

Massoud Malek Lemma 1. For positive integers m and n , where 1 ≤ m < n, the triple < m , n > = (n2 − m2 , 2 m n, n2 + m2 ) is Pythagorean. Moreover, if m and n are relatively prime of opposite parity, then they generate a primitive triple. Basic Properties of Primitive Pythagorean Triangles In a primitive Pythagorean triangle T = (a, b, c), the following conditions hold: • The hypotenuse and one of the legs are always odd and the other leg is divisible by 4. • The hypotenuse of every PPT exceeds the odd leg by twice the square of an integer r and the even leg by the square of an odd integer s, c = a + 2 r 2 = b + s2 Generating Matrix ⎛ ⎞ 1 0 1 Consider the matrix G = ⎝2 2 2⎠ and the vector u [m, n] = (m2 , mn, n2 ), where m is 0 2 2 odd and gcd (m, n) = 1. Then ⎛ ⎞ 1 0 1     u [m, n] G = m2 , mn, n2 ⎝2 2 2⎠= m2 +2 mn, 2 mn + 2 n2 , m2 +2 mn+2 n2 = < n, m + n >. 0 2 2 Proposition 1. Let P be the set of all PPTs. For fixed positive integers m0 and n0 , , where m0 is odd, define the following sets of PPTs: Rm0 = {Tn = (an , bn , cn ) = u[m0 , n] G : n = 1, 2, 3, . . . , gcd (m0, n) = 1} , Sn0 = {Tm = (am , bm , cm ) = u[m, n0 ] G : m = 1, 3, 5, . . . , gcd (m, n0) = 1} . and Then Rm0 ∩ Sn0 = u[m0 , n0 ] G, whenever gcd(m0 , n0 ) = 1; also for all Tn ∈ Rm0 and Tm ∈ Sn0 , cn − bn = m20 and cm − am = 2 n0 2 ; and finally for i1 = i2 and j1 = j2 , P= ∞  i=0 R2 i+1 = ∞  Sj , R2 i1 +1 ∩ R2 i2 +1 = ∅ , S2 j1 ∩ S 2 j2 = ∅ . j=1 Moreover, R1 contains all the PPTs, where the hypotenuse exceeds its even leg by one; and S1 contains all the PPTs, where the hypotenuse exceeds its odd leg by two. Proof. The identity u [m, n] G = < n, m + n > and Lemma 1 imply that any PPT can be obtained from the product of the vector u [m, n] and the generating matrix G. Thus P= ∞  i=0 R2 i+1 = ∞

Primitive Pythagorean codes We also conclude that if gcd (m0, n0 ) = 1, then Rm0 ∩ Sn0 contains only one PPT, which is u[m0 , n0 ] G. From the definitions of u [r, s] G, we obtain   T = (a , b , c) = u [r, s] G = r 2 + 2 r s, 2 r s + 2 s2, r 2 + 2 r s + 2 s2 Notice that c − b = r 2 and c − a = 2 s2 . Thus for the same a , b , and c ; r and s must be unique. Hence for i1 = i2 and j1 = j2 , R2 i1 +1 ∩ R2 i2 +1 = ∅ and S2 j1 ∩ S 2 j2 = ∅. Finally, from c − b = r 2 and c − a = 2 s2 , we conclude that cn − bn = (2 i + 1)2 and cm − am = 2 j 2 . Hence only R1 contains all the PPTs, where the hypotenuse exceeds its even leg by one; and only S1 contains all the PPTs, where the hypotenuse exceeds its odd leg by two. Proposition 2. Let T = (a, b, c) be a PPT. a − m20 (i) If T ∈ Rm0 ; then T = u m0 , 2 m0 (ii) If T ∈ Sn0 ; then T = u − n0 + G= a2 − m40 a2 + m40 , a, 2 m20 2 m20 n20 + a , n0 G = a , 2 n0 . n20 + a , a + 2 n20 . Proof. (i) If T ∈ Rm0 ; then there exists a positive integer n with gcd (m0 , n) = 1 such that   T = (a, b, c) = u[m0 , n] G = m20 + 2 m0 n , 2 n (m0 + n) , m20 + 2 n (m0 + n) . From a = m20 + 2 m0 n , we obtain T = u m0 , n= a − m20 2 m0 a − m20 . Hence 2 m0 G= a, a2 − m40 a2 + m40 , 2 m20 2 m20 . (ii) If T ∈ Sn0 ; then there exists an odd number m with gcd (m, n0) = 1 such that   T = (a, b, c) = u[m, n0 ] G = m2 + 2 m n0 , 2 n0 (m + n0 ) , m2 + 2 n0 (m + n0 ) . By solving the quadratic equation a = m2 + 2 m n0 for a positive m , we obtain m= − n0 + n20 + a . Hence T = u − n0 + n20 + a , n0 G = n20 + a , a + 2 n20

Massoud Malek From the fact that the last digit of any integer, could not be different from 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 ; we conclude that any Rm0 and Sn0 may be partitioned into a finite number of disjoint classes, based on the last digits of a , b , and c , of T = (a, b, c). The first 30 PPTs Tn = (an , bn , cn ), generated by [1, n, n2 ] G : (3 , 4 , 5) (5 , 2 , 3) (7 , 4 , 5) (9 , 0 , 1) (1 , 0 , 1) 3 4 5 5 12 13 7 24 25 9 40 41 11 60 61 13 84 85 15 112 113 17 144 145 19 180 181 21 220 221 23 264 265 25 312 313 27 364 365 29 420 421 31 480 481 33 544 545 35 612 613 37 684 685 39 760 761 41 840 841 43 924 925 45 1012 1013 47 1104 1105 49 1200 1201 51 1300 1301 53 1404 1405 55 1512 1513 57 1624 1625 59 1740 1741 61 1860 1861 The above table shows that the set of Tn , is partitioned into five disjoint classes, with coset leaders: (3 , 4 , 5), (5 , 2 , 3), (7 , 4 , 5), (9 , 0 , 1), and (1 , 0 , 1). According to Proposition 1, cn − bn = 1. From an = 1 + 2 n, bn = 2 n (1 + n), and cn = 1 + 2 n (1 + n), one may readily show the following identities which appear in the above table: an+1 = an + 2, a5 k+n = an + 10 k, an+6 = an + 12, a2n = bn + cn , and a6 k+1 is divisible by 3. The first 30 PPTs Tm = (am , bm , cm ), generated by [ m2 , m, 1] G (Plato PPT), where m is odd: (3 , 4 , 5) (5 , 8 , 7) (5 , 2 , 7) (3 , 6 , 5) (9 , 0 , 1) 3 4 5 15 8 17 35 12 37 63 16 65 99 20 101 143 24 145 195 28 197 255 32 257 323 36 325 399 40 401 483 44 485 575 48 577 675 52 677 783 56 785 899 60 901 1023 64 1025 1155 68 1157 1295 72 1297 1443 76 1445 1599 80 1601 1763 84 1765 1935 88 1937 2115 92 2117 2303 96 2305 2499 100 2501 2703 104 2705 2915 108 2917 3135 112 3137 3363 116 3365 3599 120 3601 According to the above table, the set of Tm is partitioned into five disjoint classes, with coset leaders: (3 , 4 , 5), (5 , 8 , 7), (5 , 2 , 7), (3 , 6 , 5), and (9 , 0 , 1). According to Proposition 1, cm − am = 2. From am = m2 + 2 m, bm = 2 (m + 1), and cm = m2 + 2 (m + 1), one may readily show the following identities which appear in the above table: bm+2 = bm + 4, bm+10 k = bm + 20 k, b2m = 2 (bm + cm ), and a12 k+1 is divisible by 3.

Primitive Pythagorean codes Application to Coding Theory Primitive Pythagorean triple can lend itself to Coding Theory. There are infinitely many ways to encode letters of alphabet with PPTs. To define a class of codewords, first we select either Rm0 or Sn0 . Suppose, we choose Rm0 , where m0 is a prime odd number; then we assign a positive integer k with gcd (m0, k) = 1 to each letter of the alphabet. Finally, we create a Pythagorean alphabet using the generating matrix G. Here is a Pythagorean alphabet using R7 . For the sake of simplicity, the alphabet was generated by u[7, k] G, where k = 1, 2, 3, . . . , 30, excluding k = 7, 14, 21, and 28 which are multiples of 7 . The Pythagorean alphabet is as follows: A → 63 16 65 E → 119 120 169 I → 189 340 389 M → 259 660 709 Q → 315 988 1037 U → 385 1488 1537 Y → 455 2088 2137 B → 77 36 85 F → 133 156 205 J → 203 396 445 N → 273 736 785 R → 329 1080 1129 V → 399 1600 1649 Z → 469 2220 2269 C → 91 60 109 G → 161 240 289 K → 217 456 505 O → 287 816 865 S → 357 1276 1325 W → 413 1716 1765 D → 105 88 137 H → 175 288 337 L → 231 520 569 P → 301 900 949 T → 371 1380 1429 X → 427 1836 1885 This set contains five different disjoint classes: (3 , 6 , 5) (7 , 6 , 5) (1 , 0 , 9) (5 , 8 , 7) AF J N W BKOSX C LT GP DH QU Y (9 , 0 , 9) EI M RV Z Error Detection The fact that R7 is partitioned into five disjoint classes; the received codeword must be in one of those five classes. If the last digits of a , b , or c do not match the digits of any of the coset leaders, the received codeword may be corrupted. Once the error is detected, it could eventually be corrected either directly or by a retransmission. It is customary that all codewords have the same length. We could achieve this task by adding some digits, such as zeros or ones at the beginning or the end of the shorter codewords. Data Compression Sometimes, it is necessary to shorten the length of the codewords without compromising the integrity of the message. According to Proposition 1, Rm0 contains all the PPTs, where the hypotenuse exceeds its even leg by m20 ; and Sn0 contains all the PPTs, where the hypotenuse exceeds its odd leg by 2 n20 . Removing the hypotenuse of the encrypted code in these sets, would not alter the message and its integrity. Notice that in R7 , c − b = 49 = 7 2 , for all c’s and b’s; so the alphabet could be shorten, by removing all the hypotenuses. According to Proposition 2, from the odd leg a of the a − 49 , the number assigned to the letter which was encoded codeword, we obtain k =

Massoud Malek with the generating matrix G. Therefore we could also remove the even leg b . In order to be able to detect some transmission errors, we should add the last two digits of the coset leader of the class which contains the codeword. Here is the short form of the alphabet with parity-check digits: A → 63 65 G → 161 09 M → 259 09 S → 357 65 Y → 455 87 B → 77 65 C → 91 09 D → 10 87 H → 175 87 I → 189 09 J → 203 65 N → 273 65 O → 287 65 P → 301 09 T → 371 09 U → 385 87 V → 399 09 Z → 469 09 E → 119 65 K → 217 65 Q → 315 87 W → 413 65 F → 133 65 L → 231 09 R → 329 09 X → 427 65 Error Correction and Decoding Suppose the codewords w1 = 133 67 and w2 = 359 75 were received. Since (3, 6, 7) and (9, 7, 5) are not coset leaders; but 133 65 is in our table, generated by u[7, 6] G, representing the letter F ; and 359 65 is very close to 357 75 generated by u[7, 22] G, representing the letter S. We therefore conclude that it is most likely that v1 = 133 65 and v2 = 357 65 are the transmitted codewords. Although the generating matrix G is needed to encode a message; the received codeword by itself may decode the message without the need of the inverse of the generating matrix a − 49 G. We could recreate the message, using 7, k = , and G. 14 One could obviously generate a Pythagorean alphabet, using Sn0 . To decode the message, k= − n0 + n20 + a must be used. In order to increase the probability of correcting errors, one could assign for example, three PPTs to each letter in the following way: “Choose the odd leg of the first PPT, the even leg of the second PPT, and the hypotenuse of the third PPT.” This way, if one of the legs is error-free, then the codeword may be identified. Finally, another way of increasing the probability of correcting errors and decreasing the number of retransmission; is to choose k’s with large gaps between them. This way, it is most likely that the closest codeword to the received codeword is the codeword sent. Clearly, all codewords must be converted to binary codewords, before transmission. References [1] Carmichael, R. D., 1914, “Diophantine analysis,” in second half of R. D. Carmichael, The Theory of Numbers and Diophantine Analysis, Dover Publ., 1959. [2] Edenfield, Kelly, “Pythagorean Triples.” http://jwilson.coe.uga.edu/EMT668/EMT668. Folders.F97/Edenfield/Pythtriples/Pythriples.html [3] Posamentier, Alfred; Lehmann, Ingmar (2007). The (Fabulous) FIBONACCI Num-

Primitive Pythagorean codes bers. Prometheus Books. p. 305. ISBN 978-1-59102-475-0. Received: September 27, 2013