Merit factors of the Legendre sequences

edit · history · discussion · files · short url · combinatorics number theory

Numbers

$p$

$F_p$

9/2

5/4

7/2

11:

11/6

13:

169/124

17:

289/208

19:

361/234

23:

23/10

29:

841/588

31:

961/526

37:

1369/948

41:

1681/1160

43:

1849/1250

47:

2209/1158

53:

2809/1924

59:

3481/2234

61:

3721/2540

67:

4489/3034

71:

5041/2758

73:

5329/3624

79:

6241/3878

83:

6889/4530

89:

7921/5368

97:

9409/6368

101:

10201/6900

103:

10609/6814

107:

11449/7594

109:

11881/8028

113:

12769/8624

127:

16129/10518

131:

17161/11210

137:

18769/12648

139:

19321/12874

149:

22201/14948

151:

22801/14678

157:

24649/16588

163:

26569/17850

167:

27889/17174

173:

29929/20124

179:

32041/21178

181:

32761/22020

191:

36481/22326

193:

37249/25024

197:

38809/26068

199:

39601/25518

211:

44521/29746

223:

49729/32702

227:

51529/34218

229:

52441/35188

233:

54289/36424

239:

57121/35438

241:

58081/38960

251:

63001/41578

257:

66049/44288

263:

69169/44190

269:

72361/48508

271:

73441/47646

277:

76729/51428

281:

78961/52920

283:

80089/53530

293:

85849/57524

307:

94249/62994

311:

96721/60230

313:

97969/65624

317:

100489/67308

331:

109561/73226

337:

113569/76048

347:

120409/80258

349:

121801/81548

353:

124609/83424

359:

128881/81718

367:

134689/89078

373:

139129/93124

379:

143641/95994

383:

146689/94502

389:

151321/101268

397:

157609/105468

401:

160801/107600

409:

167281/111928

419:

175561/116378

421:

177241/118580

431:

185761/118726

433:

187489/125424

439:

192721/126038

443:

196249/130914

449:

201601/134848

457:

208849/139688

461:

212521/142140

463:

214369/142702

467:

218089/145186

479:

229441/145638

487:

237169/157926

491:

241081/160130

499:

249001/166354

503:

253009/163630

509:

259081/173228

521:

271441/181480

523:

273529/182514

541:

292681/195660

547:

299209/199874

557:

310249/207388

563:

316969/210794

569:

323761/216408

571:

326041/217570

577:

332929/222528

587:

344569/229626

593:

351649/235024

599:

358801/231998

601:

361201/241400

607:

368449/244054

613:

375769/251124

617:

380689/254408

619:

383161/255698

631:

398161/263886

641:

410881/274560

643:

413449/276130

647:

418609/273094

653:

426409/284924

659:

434281/288594

661:

436921/291940

673:

452929/302624

677:

458329/306228

683:

466489/311314

691:

477481/318650

701:

491401/328300

709:

502681/335828

719:

516961/333454

727:

528529/350894

733:

537289/358924

739:

546121/364458

743:

552049/363230

751:

564001/373870

757:

573049/382788

761:

579121/386840

769:

591361/395008

773:

597529/399124

787:

619369/413338

797:

635209/424268

809:

654481/437128

811:

657721/438618

821:

674041/450180

823:

677329/451294

827:

683929/456106

829:

687241/458988

839:

703921/456654

853:

727609/485924

857:

734449/490488

859:

737881/492106

863:

744769/491830

877:

769129/513628

881:

776161/518320

883:

779689/520530

887:

786769/514958

907:

822649/549194

911:

829921/542286

919:

844561/559398

929:

863041/576288

937:

877969/586248

941:

885481/591260

947:

896809/598458

953:

908209/606424

967:

935089/622774

971:

942841/626650

977:

954529/637328

983:

966289/636102

991:

982081/652038

997:

994009/663668

Definition

For an odd prime $p$, the Legendre sequence $u^{(p)}=(u_0,\ldots,u_{p-1})$ is defined by $u_0=1$ and $u_j=\left(\frac{j}{p}\right)$ for $1\leq j<p$, where $\left(\frac{\cdot}{p}\right)$ is the Legendre symbol [3]. This table holds its aperiodic merit factor $F_p$.

Parameters

$p$

— prime length ($p$ is an odd prime)

Formulas

(1)

$F_p=p^2/(2\sum_{k=1}^{p-1}c_k^2)$, where $c_k=\sum_{j=0}^{p-1-k}u_ju_{j+k}$ for $1\leq k<p$.

(2)

If $U_p(x)=\sum_{j=0}^{p-1}u_jx^j$ and $\|U_p\|_4^4$ denotes the integral of $|U_p(z)|^4$ over $|z|=1$ with normalized Haar measure, then $F_p=p^2/(\|U_p\|_4^4-p^2)$, since $\|U_p\|_4^4=c_0^2+2\sum_{k=1}^{p-1}c_k^2$ with $c_0=\sum_{j=0}^{p-1}u_j^2=p$.

(3)

For the unrotated Legendre sequence, $F_p\to 3/2$ as $p\to\infty$ [2].

Comments

(4)

The sequence is not cyclically rotated, and the merit factor is the aperiodic one. The periodic merit factor is a different quantity.

(5)

The merit factor convention and the Legendre sequence family are those studied by Golay [1] and by Hoholdt and Jensen [2].

(6)

The polynomial $U_p$ from (2) satisfies $U_p(x)=1+f_p(x)$, where $f_p$ is the Fekete polynomial with the same prime parameter.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.arith.misc import kronecker_symbol
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ

def legendre_merit_factor(p):
    u = [ZZ(1)] + [ZZ(kronecker_symbol(j, p)) for j in range(1, p)]
    denominator = ZZ(0)
    for k in range(1, p):
        c = sum(u[j] * u[j + k] for j in range(p - k))
        denominator += c * c
    return QQ(p * p) / QQ(2 * denominator)

legendre_merit_factor(1009)      # the next prime after this table

References

[1]

M. J. E. Golay, The merit factor of Legendre sequences, IEEE Transactions on Information Theory 29 (1983), no. 6, 934-936. (doi)

[2]

T. Hoholdt and H. E. Jensen, Determination of the merit factor of Legendre sequences, IEEE Transactions on Information Theory 34 (1988), no. 1, 161-164. (doi)

Links

[3]

Wikipedia: Legendre symbol

Similar tables

Fekete polynomials $f_p$ — have the same Legendre-symbol coefficients for positive powers, but store the polynomial with zero constant term rather than the merit factor of the length-$p$ sequence with $u_0=1$

Shapiro polynomials $P_n$ — use the Rudin-Shapiro sign rule for another family of binary sequences with small aperiodic autocorrelations

Complementary Shapiro polynomials $Q_n$ — form the second polynomial sequence in the same Rudin-Shapiro pair, another family of binary sequences with small aperiodic autocorrelations

Data properties

Entries are of type: rational number

How well the digits are known: exact

Table is complete: no (it holds every odd prime $p<1000$, a small-prime range that keeps the exact $O(p^2)$ autocorrelation computation tractable to rerun)

How they were obtained:

The generator computes the Legendre sequence from exact Legendre symbols and forms the aperiodic autocorrelations by integer arithmetic. The values are exact rational numbers.

The run checked every value against the same sequence built by Euler's criterion rather than Sage's Legendre symbol, against the known small values for $p=3,5,7,11,13$, and against the $L^4$-norm formula computed from all ordered coefficient pairs.