Integer sequences and semidefinite programming
type: Item
instance of: scholarly article
zbMATH Open document ID: 0960.11004
publication date: 2001-04-01T00:00:00Z
Mathematics Subject Classification ID: 11B25
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 1583175
zbMATH Keywords: discrepancy
zbMATH Keywords: arithmetic progression
zbMATH Keywords: semidefinite optimization
MaRDI profile type: Publication
Recommended article: Q5292090
Recommended article: Semidefinite Relaxations for Integer Programming
Recommended article: Q3735470
Recommended article: Q4407449
Recommended article: Integer optimization on convex semialgebraic sets
Recommended article: Semidefinite programming and combinatorial optimization
Recommended article: Semidefinite programming in combinatorial optimization
Recommended article: Q4040221
Recommended article: Semidefinite Programming and Ramsey Numbers
author: László Lovász
title: Integer sequences and semidefinite programming
published in: Publicationes Mathematicae Debrecen
review text: A theorem of \textit{K. F. Roth} [Acta Arith. 9, 257-260 (1964; Zbl 0125.29601)] asserts that for any sequence \(x_1, \dots, x_n\) of \(\pm 1\)'s there is an arithmetical progression \(A\) such that \(|\sum _{i\in A} x_i|\gg n^{1/4} \). The proof is simple and beautiful. The author considers a related square mean, which is a linear function in the variables \(y_{ij}=x_ix_j\). Then the restriction that \(y_{ij}\) is of this form is replaced by the weaker assumption that the matrix \((y_{ij})\) is positive semidefinite, and the resulting optimization problem is solved.
reviewed by: Imre Z. Ruzsa
description: scientific article