14 votes

Current state of the Komlos conjecture on vector balancing

As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an ...
Tony Huynh's user avatar
  • 31.5k
10 votes
Accepted

Current state of the Komlos conjecture on vector balancing

For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$. Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ ...
js21's user avatar
  • 7,199
6 votes

Can we balance $2$-powers?

UPDATED. I've changed the verification strategy and computationally proved the statement for all $k\leq 30$, using the following randomized algorithm. Randomized algorithm. For a given list of $k$ ...
Max Alekseyev's user avatar
4 votes

Estimates on the discrepancy of random sequences

$\mathbb{E}[D(N; X)]$ is of order $N^{-1/2}$. This, and more precise information, follows from the analysis of the Kolmogorov-Smirnov test [1]. See, in particular, [2] and the references described on ...
Yuval Peres's user avatar
4 votes
Accepted

Typo in Soundararajan's *Bulletin of the AMS* article on Tao's resolution of The Erdos Discrepancy Problem?

I actually think there is a more significant flaw. A counterexample to the centered inequality is $\rho = \frac{1}{2}$ and $A = \{1,2,\dots,\frac{N}{2}\}$. Indeed, we always have $\sum_{n \in A, n \...
mathworker21's user avatar
3 votes

Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

As I understand it, you might be interested in a quantity called the inverse of the star-discrepancy. Given dimension $d$ and some $\varepsilon > 0$, the inverse of the star-discrepancy $n(d,\...
Kurisuto Asutora's user avatar
3 votes
Accepted

the sum of fractional parts times the ordinary powers

As Gerry already commented, your formulas are equivalent to a reciprocity theorem of Tom Apostol; see, e.g., the bibliography in this paper (Apostol's paper is too old to be on the arXiv): Your sums ...
matthias beck's user avatar
2 votes
Accepted

Distribution-free statistics on compact Lie groups

From the perspective of statisticians, I will suggest two chapters in Parthasarathy, Kalyanapuram Rangachari. Probability measures on metric spaces. Vol. 352. American Mathematical Soc., 1967. ...
Henry.L's user avatar
  • 7,971
2 votes

Bounded version of linear and quadratic Hasse--Minkowski theorem

The linear case is Siegel's lemma. I do not know the quadratic case: Cassels does not have it, perhaps O'Meara does. Note that the regulator is closely related where we seek a representation of $1$ by ...
Watson Ladd's user avatar
  • 2,419
2 votes
Accepted

Reference request - parallel rectangles discrepancy theory

Perhaps the issue is to establish a tight lowerbound for the discrepancy of $n$ points in dimension $d$ with respect to $d$-dimensional boxes. In Matousek, Jiri, ed. Geometric discrepancy: An ...
Joseph O'Rourke's user avatar
1 vote

Can we balance $2$-powers?

Fedor Petrov's comment shows than for each $k$ there are only finitely many cases for $x_1$ to check, so I wrote a program to do this. The positive answer is already obtained for all natural $k\le 10$....
Alex Ravsky's user avatar
  • 4,102
1 vote
Accepted

Minimize total area bounded by $N$ lines in general position

I wound up contacting Dr. János Pach (an expert in relevant fields) regarding the problem on the recommendation of my first professor. Apparently the problem (originally in a slightly different form) ...
Lieutenant Zipp's user avatar
1 vote

Is the bound of Spencer on discrepancy tight?

Yes, the bound is tight, and here is a proof sketch. In fact, we will show that a random sequence of subsets $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ provides the lower bound up to constants. ...
yangpliu's user avatar
  • 101
1 vote

Discrepancy of the Halton set

It is true that in general there is a difference between "sets" and "sequences". The later, unlike sets, may have repeating elements, and also unlike sets, the order of elements ...
Arturo Ortiz Tapia's user avatar
1 vote

Bounded version of linear and quadratic Hasse--Minkowski theorem

For the first question, the answer is yes; you can find the statement and a proof in Cassels (pp 86-89). A far reaching generalization was obtained by J. Vaaler in 1987 concerning the height of a ...
WKC's user avatar
  • 646
1 vote

Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

This may not be what the OP seeks, but the paper below contains quite a bit of detailed numberical tables for low star-discrepancy sets. Star discrepancy $d^*$ takes the supremum over rectangles that ...
Joseph O'Rourke's user avatar
1 vote

Quantified imbalance in signed graphs

Ad 1: I take this to ask for whether 'horribly imbalanced' graphs even exist, and, more generally, what can be said about the necessary conditions you imposed on them. This is what this answer/comment ...
Peter Heinig's user avatar
  • 6,001
1 vote

Occurrence of simultaneous small remainders?

This is not always true. Suppose that $c_1+c_2=c_0$. Then $pc_1+pc_2\equiv pc_0\pmod{n}$. Hence if $pc_1\bmod n$, $pc_2\bmod n$ are in $[0, n^r]$, then $pc_0\bmod n$ is in $[0, 2n^r]$, which falls ...
Jan-Christoph Schlage-Puchta's user avatar
1 vote

An extremal combinatorics problem involving column summation

If you relax the power-of-two condition, you can contrive examples for the $\beta = 1/2$ and $\alpha = 1$ case that require all columns to be used. Choose a large prime $p$. Let $A$ be the $p \times ...
tmyklebu's user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible