Multiplicative sequences

From Polymath1Wiki
Jump to: navigation, search

Case C=2

Any completely-multiplicative sequence of length [math]247[/math] has discrepancy more than [math]2[/math].

Data and plots

There are 500 sequences of length [math]246[/math] with discrepancy [math]2[/math], all of which agree at primes up to and including [math]67[/math]. Here is one example:

0 + - - + - + - - + + + - - + + + - -
+ - + - - + + + - - + - + - - + + + -
- + + - - - + - + - - + - + - + + - +
- - + + + - - + + + - - + - - - + + -
+ - - + - + + - + + + - - - + + - - +
- + - - + + - - + + - - + - + + + - -
+ + + - - + - + - + + - + - - + - + -
- + + + - - - + + + - + - - - - + + +
- - + - + + - - + + - - - + + - - + -
+ - + + - + - + + - + - - + + + - - +
+ - - - + - + - - + - + + - + + - - -
+ + - + + - + + - - - - + - + + + + -
- - - + - + + + + - - - + + - - + - -


Here are the values this sequence takes at the first few primes. The primes up to 101 that go to -1 are 2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 71, 83, 89, 97, 101. The primes less than 100 that go to 1 are 11, 19, 29, 31, 53, 59, 61, 73, 79.

The total number of such multiplicative sequences for each length can be generated with Alec's python script.

Here is a plot of this data, and a plot of the log of the data, and here are the precise numbers:

length number

2 2

3 3

4 3

5 4

6 4

7 7

8 7

9 6

10 6

11 10

12 10

13 15

14 15

15 14

16 14

17 21

18 21

19 34

20 34

21 24

22 24

23 38

24 38

25 28

26 28

27 23

28 23

29 34

30 34

31 54

32 54

33 37

34 37

35 28

36 28

37 40

38 40

39 31

40 31

41 48

42 48

43 72

44 72

45 57

46 57

47 89

48 89

49 81

50 81

51 62

52 62

53 92

54 92

55 55

56 55

57 44

58 44

59 68

60 68

61 111

62 111

63 83

64 83

65 71

66 71

67 113

68 113

69 97

70 97

71 157

72 157

73 240

74 240

75 175

76 175

77 125

78 125

79 185

80 185

81 178

82 178

83 286

84 286

85 212

86 212

87 178

88 178

89 276

90 276

91 163

92 163

93 138

94 138

95 119

96 119

97 176

98 176

99 129

100 129

101 198

102 198

103 315

104 315

105 277

106 277

107 426

108 426

109 656

110 656

111 485

112 485

113 846

114 846

115 502

116 502

117 256

118 256

119 198

120 198

121 112

122 112

123 82

124 82

125 82

126 82

127 100

128 100

129 84

130 84

131 134

132 134

133 56

134 56

135 44

136 44

137 61

138 61

139 105

140 105

141 84

142 84

143 72

144 72

145 55

146 55

147 48

148 48

149 72

150 72

151 120

152 120

153 72

154 72

155 72

156 72

157 132

158 132

159 112

160 112

161 112

162 112

163 184

164 184

165 164

166 164

167 246

168 246

169 234

170 234

171 168

172 168

173 246

174 246

175 246

176 246

177 246

178 246

179 408

180 408

181 624

182 624

183 414

184 414

185 384

186 384

187 286

188 286

189 286

190 286

191 304

192 304

193 392

194 392

195 362

196 362

197 468

198 468

199 812

200 812

201 776

202 776

203 626

204 626

205 386

206 386

207 386

208 386

209 386

210 386

211 694

212 694

213 573

214 573

215 471

216 471

217 279

218 279

219 259

220 259

221 259

222 259

223 354

224 354

225 125

226 125

227 125

228 125

229 250

230 250

231 250

232 250

233 375

234 375

235 250

236 250

237 250

238 250

239 500

240 500

241 750

242 750

243 500

244 500

245 500

246 500[math]Insert formula here[/math]

247 0

And the same data in Mathematica format: {{1,1},{2,2},{3,3},{4,3},{5,4},{6,4},{7,7},{8,7},{9,6},{10,6},{11,10},{12,10},{13,15},{14,15},{15,14},{16,14},{17,21},{18,21},{19,34},{20,34},{21,24},{22,24},{23,38},{24,38},{25,28},{26,28},{27,23},{28,23},{29,34},{30,34},{31,54},{32,54},{33,37},{34,37},{35,28},{36,28},{37,40},{38,40},{39,31},{40,31},{41,48},{42,48},{43,72},{44,72},{45,57},{46,57},{47,89},{48,89},{49,81},{50,81},{51,62},{52,62},{53,92},{54,92},{55,55},{56,55},{57,44},{58,44},{59,68},{60,68},{61,111},{62,111},{63,83},{64,83},{65,71},{66,71},{67,113},{68,113},{69,97},{70,97},{71,157},{72,157},{73,240},{74,240},{75,175},{76,175},{77,125},{78,125},{79,185},{80,185},{81,178},{82,178},{83,286},{84,286},{85,212},{86,212},{87,178},{88,178},{89,276},{90,276},{91,163},{92,163},{93,138},{94,138},{95,119},{96,119},{97,176},{98,176},{99,129},{100,129},{101,198},{102,198},{103,315},{104,315},{105,277},{106,277},{107,426},{108,426},{109,656},{110,656},{111,485},{112,485},{113,846},{114,846},{115,502},{116,502},{117,256},{118,256},{119,198},{120,198},{121,112},{122,112},{123,82},{124,82},{125,82},{126,82},{127,100},{128,100},{129,84},{130,84},{131,134},{132,134},{133,56},{134,56},{135,44},{136,44},{137,61},{138,61},{139,105},{140,105},{141,84},{142,84},{143,72},{144,72},{145,55},{146,55},{147,48},{148,48},{149,72},{150,72},{151,120},{152,120},{153,72},{154,72},{155,72},{156,72},{157,132},{158,132},{159,112},{160,112},{161,112},{162,112},{163,184},{164,184},{165,164},{166,164},{167,246},{168,246},{169,234},{170,234},{171,168},{172,168},{173,246},{174,246},{175,246},{176,246},{177,246},{178,246},{179,408},{180,408},{181,624},{182,624},{183,414},{184,414},{185,384},{186,384},{187,286},{188,286},{189,286},{190,286},{191,304},{192,304},{193,392},{194,392},{195,362},{196,362},{197,468},{198,468},{199,812},{200,812},{201,776},{202,776},{203,626},{204,626},{205,386},{206,386},{207,386},{208,386},{209,386},{210,386},{211,694},{212,694},{213,573},{214,573},{215,471},{216,471},{217,279},{218,279},{219,259},{220,259},{221,259},{222,259},{223,354},{224,354},{225,125},{226,125},{227,125},{228,125},{229,250},{230,250},{231,250},{232,250},{233,375},{234,375},{235,250},{236,250},{237,250},{238,250},{239,500},{240,500},{241,750},{242,750},{243,500},{244,500},{245,500},{246,500},{247,0}}

Case C=3

The maximum length for [math]C=3[/math] is at least [math]13186[/math].

An example of that length is detailed on this page.



Length 1530:

+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--++
+--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++
+--+-+--++---+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-
+--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+++--+-+--++
+--+++--+-+--+++--+-+--+++--+++----+--+++--+-+--+++--+++--+-
+--+-+--+-+--+++--+++--+-+--+-+--+-++-+++--+++--+-+--+++--+-
+--+++--+++--+-+--+-++-+-+---++--+++--+-+--+++--+-+--+++--++
+--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++--++-+--++
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+++--+-+--++
---+++--+-+--+-+--+-+-++++--+++--+-+--+-+--+-+--+++--+++--+-
+--+++--+-+--+++--+++--+-+--+-+-++-+--++---+++----+--+++--+-
+--+++-++++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+-+--+++---++--+-+--+-+--+-+--+++--+++--+-+--+-+-++-+--++
+--+++--+-+--+++--+-+--+-+--+++--+-++-+++----+--+++--+++-++-
---+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-+--+-+--+-
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+++--+-+--+++--+++--+-+--+-+--+-++-++---+++-++-+--+-
+--+-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+++---+
+--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--+++--+-
++-+-+--+-+--+++--+++--+-+--+++--+-+--+++--++-+-+---++-+----
+--+++--+++--+-+--+++--+-+--+++--+++--+-+--+-+--+-+--+++--++
+--+-+--+-+-++-+--+++--+++--+-+--+++--+-+--+++--+++--+-+--++
+--+----++---+++--+-++-++++-+-

These are the primes sent to -1 in this example: 2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 223, 227, 233, 251, 257, 263, 277, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 433, 443, 463, 467, 487, 503, 509, 523, 547, 557, 563, 577, 587, 607, 613, 617, 643, 647, 653, 661, 673, 677, 727, 733, 743, 757, 761, 769, 773, 787, 797, 823, 827, 853, 857, 863, 877, 883, 887, 907, 937, 947, 967, 977, 983, 1013, 1021, 1033, 1063, 1087, 1093, 1097, 1103, 1117, 1123, 1153, 1163, 1187, 1213, 1217, 1223, 1237, 1259, 1277, 1283, 1297, 1303, 1307, 1327, 1423, 1427, 1433, 1447, 1483, 1487, 1493, 1511, 1523

This came from a search initialized by sending primes congruent to 2 or 3 mod 5, and the prime 5, to -1, and others to +1.

Length 852:

+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--+++--+-+--+++--+-
+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--++---+++--+-+--+-+--+++--+-+--++
+--+-+--+-+--++++-+-+--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-+--+-+--+++--+++--++---+-+--+-+--+++--+-
++-+++--+-+--+-+--+++--+-+--+++--+-+--+-+--+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+---++--+++--+++--+-+--+-+--++
+--+-+--+++--+-+--+-+--+++--+-+-++++--+-+--+-+--+++--+++--++
+--+-+--+-+--+++---++--+++--+-+--+-+--+++--+++--+++--+-+--+-
+--+++--+-+--+++--+-++-+-+--+++--+-+--+++--+-+--+----+++--++
+---++--+-+--+-++-+++--+++--+++--+-+--+----+++--+++--+++--+-
+--+-+--+++--+-+--+++-++-+--+-+--+++--+-+--+++--+-+--+-+--++
+--+++--+++--+-+--+-+--+++--+++--+-++-+-+--+-----++--+++--++
+--+-+-++-+--+++--+-+--+++--+-+--+-+--+++--+-+--+++--+-+--+-
+-++++--+++-

These are the primes sent to -1 in this example: 2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 151, 157, 163, 167, 173, 193, 223, 227, 233, 257, 263, 277, 281, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 397, 433, 443, 457, 463, 467, 487, 499, 503, 523, 547, 557, 563, 577, 587, 593, 607, 613, 641, 643, 647, 653, 673, 677, 727, 733, 743, 769, 773, 787, 797, 823, 827.

This came from a search initialized by sending primes congruent to 2 or 3 mod 5 to -1 and others to +1.

Note that the only primes not congruent to 2 or 3 that are sent to -1 are 151, 281, 499, 641 and 769. [Are there some that are congruent to 2 or 3 that are sent to 1? If so, which are they?]

Length 819:

+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-++--+--+-++-++--+-+--++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+-++-+---++++--++---++--+--+-++--++-
-+++--+-++-+---+--+--++++-++-+-+----+-+++++--+-+--+---+++++-
+--+-++-+----+++-++--+-++--+--+-+++--+-+--+++---+-++--+--+-+
+-++----++-+++---++-+++-+--+-+--++-++-+

The primes that go to -1 in this example are:

2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 73, 83, 101, 107, 113, 127, 131, 137, 149, 151, 167, 197, 199, 223, 229, 233, 239, 251, 257, 263, 271, 293, 311, 317, 331, 353, 359, 367, 379, 389, 397, 401, 421, 449, 457, 463, 467, 479, 487, 491, 557, 563, 569, 587, 593, 599, 619, 631, 643, 647, 653, 661, 673, 677, 691, 709, 733, 743, 757, 761, 773, 787, 797, 809, 811

Length 627:

+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-+
+-++--+-++-----+-++-++--+-+++++--+-++--+--+-++--+--+-++-++--
+-++-----+-++-++--+-++-+++-+-+---+--+-++--+--+-++-+++-+-+-+-
+--+-++--++-+-++-+---+-++--+--+-++-++-++-+--+++---++--+--+-+
+--+--+-++-+++-+-++--+--+--++----+-++-+++-+-++--+----++-++--
++++-++--+-+---+--+-++-++--+-++-++--+-++--+---+++--+--+++--+
+--+++---+--+-++-+--+-+++-++--+-++---+-+-++--+--+-++-++--+++
---+--+-+++-+--+--+-+++--+++--+-+--+-++++---++-++--+-++--+--
+-++-+---+-++-++--+-+++-+---++---+--+--++++--+-++--+-++----+
++-+-++-++--+-++--+----++-++--+--+-++--+-+++-+--+-++--+-++-+
+-+---+-++--+--+++--+++-+++

A sequence of length 545 that agrees with the maximal discrepancy-2 sequences at primes up to and including 67:

+--+-+--+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--++
+--+++--+-+--+-+--+-++-+++---++--+-++-++--++--+--++--+++--+-
+-++-+--+-+--+++---++--+-+--+++--+-++--++-+-++--+-+-++-+-+--
+--+++--++--+--++---++-++---++-+--++-++-+--+++--+-+--+++--++
+--+----+++--+-+--+++--+-++-+----+++-++----++++-++--++-+--+-
+-++-++--++---++-++----+--+++-+--+++--+++--+--+-+++--+---+-+
+--++++-----++++--+-++-++--+-++----+-++++----+--+-++-++++-+-
-+---+-++-+-+++----++--+++--+----+-++-+++--++++-+----++++-+-
+--+-++--+-+-+-+--+-+--+++--+++--+-+----+--+++--+++-+--++-++
-+-++

This sequence is -1 at the following primes:

2, 3, 5, 7, 13, 17, 23, 37, 41, 43, 47, 67, 73, 83, 89, 101, 109, 113, 127, 137, 139, 167, 179, 191, 199, 211, 223, 227, 233, 257, 263, 271, 277, 281, 283, 313, 317, 337, 353, 359, 383, 389, 397, 421, 439, 443, 463, 491, 503, 523, 541

General Case

Here is some data on how the discrepancy of completely-multiplicative sequences grows as a function of length, depending on how missing values at prime indices are chosen.

Without loss of generality, one may always set [math]x_1=+1[/math]

Uniform choice

Here is some data when the values of [math]x_n[/math] are: a given +/-1 sequence when [math]n\gt1[/math] is one of the first [math]N[/math] primes, only the value [math]-1[/math] for [math]n[/math] any other prime, and a multiplicatively computed value when [math]n[/math] is composite.

  • N=1
    • [math]x_1=+1[/math], [math]x_2=+1[/math]: D(100)=21, D(1000)=107, D(10000)=407
    • ...
  • N=2
    • [math]x_1=+1[/math], [math]x_2=+1[/math], [math]x_3=+1[/math]: D(100)=34, D(1000)=262, D(10000)=1190
    • ...
  • N=3
    • [math]x_1=+1[/math], [math]x_2=+1[/math], [math]x_3=+1[/math], [math]x_5=+1[/math]: D(100)=25, D(1000)=413, D(10000)=2332
    • ...

Minimizing the discrepancy D up to the next prime

Here is a plot of D(n), the discrepancy as a function of length, as well as the partial sums of the first few HAP when one starts with [math]x_1=1[/math] and ask that the value at prime [math]p[/math] be either +1 or -1 depending on which allows to minimize [math]D(q)[/math], where [math]q[/math] is the next prime.

Here is a plot doing the same thing but instead starting with the first 1124 sequence as a seed.

The two plots show that the partial sums do grow at least logarithmically.

Minimizing the sum of partial HAP sums

A method to choose a value at an undertermined prime [math]p[/math] is to choose to impose [math]x_p=+1[/math] or [math]x_p=-1[/math] depending on which gave the smallest quantity [math]\ell_s(q)[/math], where [math]q[/math] is the next prime and [math]\ell_s(q):=\sum_{d=1}^q s_d(q)[/math] with [math]s_d(q)[/math] itself the partial sum of the d-HAP up to [math]q[/math].

Here is a plot obtained when setting only [math]x_1=+1[/math]. On it is shown the function [math]f(x):=\log (x)[/math] (the very flat curve), the partial sums of the sequence and its first few HAPs, and both [math]D(n)[/math] and [math]-D(n)[/math].