Laszlo Hars’ Homepage

Email: Laszlo at Hars period US

Resume [pdf]

I work in Information Security – Anti Tamper research and development.

Publications: See in my Resume

66+ Issued Patents

80+ Published Patent Applications

Numerical Solutions for the Tammes Problem (N = 2…60) [pdf]

The Tammes Problems ask to place a given number N points on the surface of the unit sphere, such that the minimum distance between these points is maximal. The referred document deals with their numerical (approximate) solutions.

The term “numerical solution” is used for

-          finding arrangements of N points on the sphere

-          with “large” shortest distances

-          by numerical optimization methods

-          starting from random initial point sets.

The found shortest distances are close to the possible maxima, and at reasonably high probabilities they are maximal.

The linked document

-          summarizes our experiments with random-restart numerical optimizations for the Tammes problems

-          compares a few publicly available numerical optimization algorithms

-          discusses several possible problem encodings

-          presents program code with diagnose/debug/verification options

-          investigates the generation of uniform- and homogenous random spherical points

-          finds symmetries in the contact graphs

-          shows various graphical representations of the results; and the programs plotting them

-          lists the best found Tammes point sets (coordinates of the points, and graphic plots)

-          presents simple, arbitrary precision methods for computing the exact minimax distances of the Tammes problem for N = 3…16, 24. (The methods for N = 10, 13, 14, 15 and 16 seem to be new.)

The solutions found by numerical optimizations all agree with the proven instances of the Tammes problem, and are better than, or the same as the best point sets published.

Below some interesting facts about the N-point Tammes Graphs, denoted with TG-<N>, are listed. (They are the contact graphs of the found best solutions of the Tammes problem – where points at the minimal distance are connected.)

-          TG-19: the smallest Tammes Graph with an isolated point

-          TG-20: is the smallest Tammes Graph with 2 isolated points

-          TG-21, 22 and 23: the smallest cases with no symmetry

-          TG-23 disproves the conjecture that the Tammes set for N = 23 is the same as it is for N = 24, with one point removed

-          TG-23: has an isolated point and 2 rhombic faces, which are almost square (their diagonals are of the same length within 0.3%)

-          TG-37: has 3 isolated points

-          TG-52, 56: have 4 isolated points…

Below are the stereographic projections of a few interesting Tammes Graphs:

Several computer programs are presented in the document for finding numerical solutions and for plotting them. They are placed into the public domain: anyone can use them for any purpose – although without our guaranties for correctness or fitness to any goals. We hope that the presented information is useful.

The table below contains the cosine of the found best minimax angular distances of the Tammes sets.

 

0

10

20

30

40

50

+1

0.4472135955

0.6994984311

0.7911186133

0.8412363430

0.8714843649

+2

−1.00000000000

0.4472135955

0.7103062586

0.7936166149

0.8433315516

0.8729667088

+3

-0.5000000000

0.5426364868

0.7228469849

0.8063976136

0.8472088654

0.8761898040

+4

-0.3333333333

0.5639503003

0.7230784683

0.8109843372

0.8482013783

0.8770043064

+5

0.0000000000

0.5926059029

0.7473986286

0.8159377715

0.8542494741

0.8807850465

+6

0.0000000000

0.6122946165

0.7542781771

0.8172481853

0.8575341669

0.8817315784

+7

0.2101383127

0.6280944150

0.7583892108

0.8248924802

0.8591223614

0.8843637376

+8

0.2612038749

0.6486958322

0.7732302623

0.8265832594

0.8592922951

0.8865557452

+9

0.3333333333

0.6731168875

0.7802814159

0.8339913224

0.8666914790

0.8878557371

+10

0.4043943252

0.6764771381

0.7815518751

0.8371620725

0.8681732091

0.8894735676

This is a draft document; any feedback is appreciated. (See the latest version here.)

Numerical Solutions for Midsize Tammes Problems: N = 61…100 [pdf]

The referred document discusses extensions of the work discussed above, including the results of our experiments and improvements of the computer program for larger cases of the Tammes problem. Somewhat arbitrarily, the range of the problem size 61…100 is referred to as “midsize”, based on their solvability on a cheap home computer. On a computer network or high-performance computers, the presented methods would lead to the numerical solutions of the Tammes problems well above this range, still using reasonable computing time.

The main contribution of the document is the drastic reduction of the size of the encoding of the Tammes problem and the resulting speedup of the computations. A computer program, which uses this optimized encoding and open source, free tools is discussed and listed in full. On a home computer, this program finds good local optima at reasonable time. They are the solutions of the Tammes problems at high probability. Still, if better solutions get known, the table will be updated.

The program is placed in the public domain, anyone can use it for any purpose.

Below the results are summarized in a table. There were test-runs for all problem sizes; 5 cases with 150,000 restarts (N = 68, 73, 77, 81, 82), the others with 50,000 restarts, but with different initial population generators. The listed version of the program found better or the same local optima, but the total number of random restarts listed in the second column of the table could be increased by 50,000, and in the aforementioned 5 cases, by 150,000.

N

Restarts

Opt. Iter#

Optimum

61

60,000

1,648

0.89200844328203

62

60,000

4,392

0.89349685056883

63

70,000

9,974

0.89503618081411

64

70,000

5,349

0.89698816753708

65

70,000

33,199

0.89825910858396

66

70,000

5,665

0.89919577748308

67

80,000

23,502

0.90119822775634

68

80,000

24,435

0.90285692152157

69

80,000

39,249

0.90383460922318

70

80,000

30,825

0.90504303680279

71

80,000

5,768

0.90639673677562

72

90,000

48,542

0.90684928543572

73

90,000

67,941

0.90957174381548

74

90,000

80,847

0.91053262350104

75

100,000

12,019

0.91139090465160

76

100,000

74,505

0.91268728948391

77

100,000

91,891

0.91353634468780

78

100,000

46,319

0.91403444541297

79

110,000

85,644

0.91619796372558

80

110,000

106,955

0.91669066788385

81

110,000

881

0.91812050592972

82

120,000

99,829

0.91921610673818

83

120,000

14,144

0.91993788202315

84

130,000

25,084

0.92015169888905

85

130,000

77,276

0.92200728603694

86

130,000

123,548

0.92271617029789

87

140,000

97,812

0.92356759726451

88

140,000

55,055

0.92419417978360

89

150,000

101,789

0.92513747511725

90

150,000

148,292

0.92623115515484

91

160,000

2,417

0.92684609213400

92

160,000

82,952

0.92700341624231

93

160,000

21,881

0.92853006727172

94

170,000

99,547

0.92900246577367

95

180,000

104,390

0.92989681194411

96

180,000

135,953

0.93046202053222

97

190,000

36,320

0.93105553713269

98

190,000

133,987

0.93123999104557

99

200,000

4,708

0.93276201266923

100

200,000

8,416

0.93341118057491

The best solutions for some N values were found too close to the total number of restarts. Shaded entries in the table indicate where less than 10% fewer restarts would miss the best solution. It shows that more restarts could actually be necessary for finding the global optima, but on a home computer it may not be practical.

This is a draft document; any feedback is appreciated. (See the latest version here.)

Numerical Solutions of the Thomson-P Problems [pdf]

This document reports related work to the numerical solutions of the Tammes problem, the Thomson-P family of problems.

The latest version of this document can be downloaded from here.

The objective of the Thomson problem (Thomson-1) is to determine the minimum electrostatic potential energy configuration of N electrons constrained to the surface of a unit sphere. The electrons repel each other with a force given by Coulomb's law. The physicist J. J. Thomson posed the problem in 1904. Mathematically, the objective of the Thomson problem is to minimize the sum of the reciprocals of the distances between pairs of points.

A generalization of the Thomson problem, the Thomson-P problem, is minimizing the sum of the P-th powers of the pairwise distances. For P, negative even numbers are interesting. At large -P values, the sum is dominated by the distances of the closest point-pairs, approximating the Tammes problems.

The document contains the description and the actual code of two computer programs for the numerical (approximate) solutions, using only open source, free tools. The programs perform numerical optimizations starting from pseudorandom initial sets of spherical points. When these optimizations are repeated with different seeds (the iteration- or restart numbers), different local minima could be found. The smallest of these minima in sufficiently many restarts is the global minimum, at a probability increasing with the number of restarts.

For the Thomson-1 problem of N ≤ 257 points the first presented program (written in Julia) found the best published point sets in reasonable time. The second, multithreaded program is written in C for Windows 10. It is over 40 times faster, therefore it could handle more points: N ≤ 322 in reasonable running times.

Listing the coordinates of the points would be too long. Instead, the iteration number of the found best solutions are given in the table below, together with the corresponding values of the objective function. From the iteration numbers as input the described programs generate the coordinates of the known best Thomson sets, in mere seconds on a home computer. The computation slows down with larger number of points, but it still takes only a couple of minutes for up to 322 points, where we stopped the experiments, due to the lack of reliable data to compare the results to.

The program in the document is placed in the public domain, anyone can use it for any purpose.

This is a draft document; any feedback is appreciated.

The tables below contain our numerical optimization results for the Thomson-1 problem, illustrating the viability of the chosen approach.

·         The first column (N) shows the number of points in the Thomson-1 set investigated.

·         The second column (i) contains the best solutions found so far according to https://en.wikipedia.org/wiki/Thomson_problem (taken 12/30/2020) − for comparison.

·         The third column shows the best Thomson solutions found with the programs listed in the document, using a cheap home computer.

·         The 4th column of the table (Iter#) has the iteration numbers of our optimization program, at which the optimum was found. The coordinates of the corresponding Thomson sets can be printed with the presented programs in just seconds on a home PC.

The solutions found by the discussed program agreed with the best published results for all N ≤ 322. For problem sizes, for which there are no reliable published solutions, some of our tabulated results could be suboptimal, to be improved with more restarts on faster computational platforms.

N

   EiEi

Num-Opt

Iter#

2

0.500000000

 

 

3

1.732050808

1.7320508075689

1

4

3.674234614

3.6742346141748

1

5

6.474691495

6.4746914946882

1

6

9.985281374

9.9852813742386

1

7

14.452977414

14.452977414221

1

8

19.675287861

19.675287861233

1

9

25.759986531

25.759986531270

1

10

32.716949460

32.716949460148

1

11

40.596450510

40.596450508191

1

12

49.165253058

49.165253057629

1

13

58.853230612

58.853230611702

1

14

69.306363297

69.306363296626

1

15

80.670244114

80.670244114294

1

16

92.911655302

92.911655302545

1

17

106.050404829

106.05040482862

1

18

120.084467447

120.08446744749

1

19

135.089467557

135.08946755668

1

20

150.881568334

150.88156833376

1

21

167.641622399

167.64162239927

1

22

185.287536149

185.28753614931

1

23

203.930190663

203.93019066288

1

24

223.347074052

223.34707405181

1

25

243.812760299

243.81276029877

1

26

265.133326317

265.13332631736

1

27

287.302615033

287.30261503304

1

28

310.491542358

310.49154235820

1

29

334.634439920

334.63443992042

1

30

359.603945904

359.60394590376

1

31

385.530838063

385.53083806330

1

32

412.261274651

412.26127465053

1

33

440.204057448

440.20405744765

1

 

N

EiEi

Num-Opt

Iter#

34

468.904853281

468.90485328134

1

35

498.569872491

498.56987249065

1

36

529.122408375

529.12240837541

1

37

560.618887731

560.61888773104

9

38

593.038503566

593.03850356645

10

39

626.389009017

626.38900901682

3

40

660.675278835

660.67527883462

1

41

695.916744342

695.91674434189

1

42

732.078107544

732.07810754367

1

43

769.190846459

769.19084645916

1

44

807.174263085

807.17426308463

1

45

846.188401061

846.18840106108

1

46

886.167113639

886.16711363919

1

47

927.059270680

927.05927067971

1

48

968.713455344

968.71345534379

1

49

1011.557182654

1011.5571826536

1

50

1055.182314726

1055.1823147263

1

51

1099.819290319

1099.8192903189

1

52

1145.418964319

1145.4189643193

2

53

1191.922290416

1191.9222904162

1

54

1239.361474729

1239.3614747292

1

55

1287.772720783

1287.7727207827

1

56

1337.094945276

1337.0949452757

3

57

1387.383229253

1387.3832292528

1

58

1438.618250640

1438.6182506404

1

59

1490.773335279

1490.7733352787

4

60

1543.830400976

1543.8304009764

1

61

1597.941830199

1597.9418301990

1

62

1652.909409898

1652.9094098983

2

63

1708.879681503

1708.8796815033

1

64

1765.802577927

1765.8025779273

1

65

1823.667960264

1823.6679602639

1

66

1882.441525304

1882.4415253042

1

 

N

EiEi

Num-Opt

Iter#

67

1942.122700406

1942.1227004055

1

68

2002.874701749

2002.8747017487

3

69

2064.533483235

2064.5334832348

6

70

2127.100901551

2127.1009015506

1

71

2190.649906425

2190.6499064258

1

72

2255.001190975

2255.0011909750

1

73

2320.633883745

2320.6338837454

3

74

2387.072981838

2387.0729818383

1

75

2454.369689040

2454.3696890396

1

76

2522.674871841

2522.6748718414

1

77

2591.850152354

2591.8501523539

1

78

2662.046474566

2662.0464745663

52

79

2733.248357479

2733.2483574788

5

80

2805.355875981

2805.3558759812

1

81

2878.522829664

2878.5228296641

1

82

2952.569675286

2952.5696752865

1

83

3027.528488921

3027.5284889211

2

84

3103.465124431

3103.4651244308

2

85

3180.361442939

3180.3614429386

1

86

3258.211605713

3258.2116057128

4

87

3337.000750014

3337.0007500145

17

88

3416.720196758

3416.7201967584

4

89

3497.439018625

3497.4390186247

2

90

3579.091222723

3579.0912227228

2

91

3661.713699320

3661.7136993200

1

92

3745.291636241

3745.2916362407

1

93

3829.844338421

3829.8443384214

2

94

3915.309269620

3915.3092696204

9

95

4001.771675565

4001.7716755650

1

96

4089.154010060

4089.1540100556

1

97

4177.533599622

4177.5335996222

1

98

4266.822464156

4266.8224641562

1

99

4357.139163132

4357.1391631318

1

 

N

EiEi

Num-Opt

Iter#

100

4448.350634331

4448.3506343313

1

101

4540.590051694

4540.5900516944

1

102

4633.736565899

4633.7365658987

1

103

4727.836616833

4727.8366168330

5

104

4822.876522746

4822.8765227487

9

105

4919.000637616

4919.0006376157

18

106

5015.984595705

5015.9845957047

7

107

5113.953547724

5113.9535477138

8

108

5212.813507831

5212.8135078306

1

109

5312.735079920

5312.7350799202

1

110

5413.549294192

5413.5492941924

6

111

5515.293214587

5515.2932145866

1

112

5618.044882327

5618.0448823266

3

113

5721.824978027

5721.8249780271

12

114

5826.521572163

5826.5215721627

4

115

5932.181285777

5932.1812857773

8

116

6038.815593579

6038.8155935785

76

117

6146.342446579

6146.3424465786

7

118

6254.877027790

6254.8770277896

10

119

6364.347317479

6364.3473174792

22

120

6474.756324980

6474.7563249797

8

121

6586.121949584

6586.1219495841

1

122

6698.374499261

6698.3744992606

105

123

6811.827228174

6811.8272281741

7

124

6926.169974193

6926.1699741935

1

125

7041.473264023

7041.4732640232

24

126

7157.669224867

7157.6692248670

9

127

7274.819504675

7274.8195046756

12

128

7393.007443068

7393.0074430680

6

129

7512.107319268

7512.1073192683

19

130

7632.167378912

7632.1673789125

1

131

7753.205166941

7753.2051669406

10

132

7875.045342797

7875.0453427971

8

133

7998.179212898

7998.1792128984

9

 

N

EiEi

Num-Opt

Iter#

134

8122.089721194

8122.0897211942

7

135

8246.909486992

8246.9094869920

1

136

8372.743302539

8372.7433025386

1

137

8499.534494782

8499.5344947815

4

138

8627.406389880

8627.4063898801

3

139

8756.227056057

8756.2270569530

9

140

8885.980609041

8885.9806090406

1

141

9016.615349190

9016.6153491899

8

142

9148.271579993

9148.2715799935

9

143

9280.839851192

9280.8398511922

52

144

9414.371794460

9414.3717944599

7

145

9548.928837232

9548.9288372318

10

146

9684.381825575

9684.3818255749

3

147

9820.932378373

9820.9323783732

1

148

9958.406004270

9958.4060042699

6

149

10096.859907397

10096.859907397

1

150

10236.196436701

10236.196436701

7

151

10376.571469275

10376.571469275

6

152

10517.867592878

10517.867592878

83

153

10660.082748237

10660.082748236

54

154

10803.372421141

10803.372421141

8

155

10947.574692279

10947.574692279

8

156

11092.798311456

11092.798311456

143

157

11238.903041156

11238.903041156

237

158

11385.990186197

11385.990186197

1

159

11534.023960956

11534.023960956

27

160

11683.054805549

11683.054805549

11

161

11833.084739465

11833.084739465

28

162

11984.050335814

11984.050335814

37

163

12136.013053220

12136.013053220

12

164

12288.930105320

12288.930105320

14

165

12442.804451373

12442.804451373

16

166

12597.649071323

12597.649071323

123

 

N

EiEi

Num-Opt

Iter#

167

12753.469429750

12753.469429750

5

168

12910.212672268

12910.212672268

10

169

13068.006451127

13068.006451127

11

170

13226.681078541

13226.681078540

165

171

13386.355930717

13386.355930717

21

172

13547.018108787

13547.018108787

62

173

13708.635243034

13708.635243034

22

174

13871.187092292

13871.187092292

1

175

14034.781306929

14034.781306929

32

176

14199.354775632

14199.354775632

17

177

14364.837545298

14364.837545298

569

178

14531.309552587

14531.309552588

70

179

14698.754594220

14698.754594220

8

180

14867.099927525

14867.099927525

82

181

15036.467239769

15036.467239769

6

182

15206.730610906

15206.730610906

4

183

15378.166571028

15378.166571028

8

184

15550.421450311

15550.421450311

1036

185

15723.720074072

15723.720074072

280

186

15897.897437048

15897.897437048

1

187

16072.975186320

16072.975186320

9

188

16249.222678879

16249.222678879

514

189

16426.371938862

16426.371938864

22

190

16604.428338501

16604.428338501

19

191

16783.452219362

16783.452219363

29

192

16963.338386460

16963.338386461

7

193

17144.564740880

17144.564740880

81

194

17326.616136471

17326.616136471

184

195

17509.489303930

17509.489303930

18

196

17693.460548082

17693.460548082

70

197

17878.340162571

17878.340162571

7004

198

18064.262177195

18064.262177195

113

199

18251.082495640

18251.082495640

196

200

18438.842717530

18438.842717530

245

 

N

EiEi

Num-Opt

Iter#

201

18627.591226244

18627.591226244

3386

202

18817.204718262

18817.204718262

60

203

19007.981204580

19007.981204580

274

204

19199.540775603

19199.540775603

651

205

 

19392.369152388

12

206

 

19585.955856549

272

207

 

19780.656909314

62

208

 

19976.203261203

237

209

 

20172.754680661

578

210

 

20370.251615129

693

211

 

20568.740602776

280

212

20768.053085964

20768.053085964

488

213

 

20968.612025491

74

214

21169.910410375

21169.910410375

363

215

 

21372.348789341

366

216

21575.596377869

21575.596377869

53

217

21779.856080418

21779.856080418

27

218

 

21985.263948921

182

219

 

22191.485474814

155

220

 

22398.655602531

174

221

 

22606.881547259

23

222

 

22816.025570249

57

223

 

23026.165881160

8

224

 

23237.244873487

3

225

 

23449.436460667

12

226

 

23662.511122654

221

227

 

23876.576893718

136

228

 

24091.578985867

36

229

 

24307.599313290

288

230

 

24524.485350945

139

231

 

24742.382494768

126

232

24961.252318934

24961.252318934

608

233

 

25181.057399530

1

 

N

EiEi

Num-Opt

Iter#

234

 

25401.931786640

92

235

 

25623.763144201

37

236

 

25846.500563152

136

237

 

26070.367015459

898

238

 

26295.126047904

1221

239

 

26520.874117442

444

240

 

26747.508205092

9

241

 

26975.190283978

756

242

 

27203.799285553

1886

243

 

27433.367352376

418

244

 

27663.905112181

1355

245

 

27895.540745391

355

246

 

28128.051464319

5421

247

 

28361.532777263

17

248

 

28596.052102948

1213

249

 

28831.473909851

575

250

 

29067.889163423

940

251

 

29305.233861625

5335

252

 

29543.522868125

197

253

 

29782.917364395

84

254

 

30023.222861843

4728

255

30264.424251281

30264.424251281

307

256

30506.687515847

30506.687515847

6649

257

30749.941417346

30749.941417346

9864

Best Results of the Julia Program

N

EiEi

Num-Opt

Iter#

258

 

30994.2135774868

611

259

 

31239.4423068662

1123

260

 

31485.5781917802

1760

261

 

31732.7427877295

3223

262

 

31980.8518238660

1199

263

 

32229.9148956472

2913

264

 

32479.9081411766

249

265

 

32731.0123974668

6659

266

 

32982.9836290832

2588

267

 

33235.9620660390

633

268

 

33489.8744849436

3243

269

 

33744.8007327701

2598

270

 

34000.6484970195

40677

271

 

34257.4417381447

8915

272

34515.193292681

34515.1932926817

10303

273

 

34774.2578509450

658

274

 

35034.0334667000

2803

275

 

35294.8940512130

14388

276

 

35556.6333035795

17841

277

 

35819.3408109533

1006

278

 

36083.0368937559

2103

279

 

36347.6584257292

1587

 

N

EiEi

Num-Opt

Iter#

280

 

36613.2695900773

1005

281

 

36879.8056153435

3166

282

37147.294418462

37147.2944184620

14968

283

 

37416.0757427823

1101

284

 

37685.6897932422

1326

285

 

37956.2394559865

8052

286

 

38227.6733205442

4850

287

 

38500.1343322855

1856

288

 

38773.5812836889

17850

289

 

39048.0491867372

15313

290

 

39323.4100620378

22241

291

 

39599.7118168330

10848

292

39877.008012909

39877.0080129083

1624

293

 

40155.3490760206

1974

294

 

40434.7622974846

1280

295

 

40715.1417167072

2166

296

 

40996.4139085292

654

297

 

41278.7032930107

1894

298

 

41561.9207687963

25409

299

 

41846.0811834311

2832

300

 

42131.2641372452

44534

 

N

EiEi

Num-Opt

Iter#

301

 

42417.3566298396

45153

302

 

42704.4937584797

10025

303

 

42992.5289668779

6886

304

 

43281.5133649633

22859

305

 

43571.5504536883

14785

306

43862.569780797

43862.5697807962

78567

307

 

44154.5477059508

8530

308

 

44447.4530563589

1376

309

 

44741.5642838065

2714

 310

 

45036.4985722224

25326

311

 

45332.4021055010

1139

312

45629.313804002

45629.3138040044

48767

313

 

45927.1925470308

38645

314

 

46225.9797575717

35275

315

46525.825643432

46525.8256434321

173295

316

 

46826.5884028806

48055

317

47128.310344520

47128.3103445197

69909

318

47431.056020043

47431.0560200432

31743

319

 

47734.8137639722

9808

320

 

48039.4689301648

4665

321

 

48345.1609527838

65053

322

 

48651.7621823975

7427

Best Results of the Multithreaded C Program