Digital Commons Network^™

On An Effective Variation Of Kronecker's Approximation Theorem, Lenny Fukshansky

CMC Faculty Publications and Research

Let Λ ⊂ Rn be an algebraic lattice, coming from a projective module over the ring of integers of a number field K. Let Z ⊂ Rn be the zero locus of a finite collection of polynomials such that Λ |⊂ Z or a finite union of proper full-rank sublattices of Λ. Let K1 be the number field generated over K by coordinates of vectors in Λ, and let L1, . . . , Lt be linear forms in n variables with algebraic coefficients satisfying an appropriate linear independence condition over K1. For each ε > 0 and a ∈ Rn, …

On The Hardness Of Counting And Sampling Center Strings, Christina Boucher, Mohamed Omar

All HMC Faculty Publications and Research

Given a set S of n strings, each of length ℓ, and a nonnegative value d, we define a center string as a string of length ` that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of center strings for a given set of strings S and input parameters n, ℓ, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, ℓ, or d is fixed leads to …

Algebraic Points Of Small Height Missing A Union Of Varieties, Lenny Fukshansky

CMC Faculty Publications and Research

Let K be a number field, Q, or the field of rational functions on a smooth projective curve over a perfect field, and let V be a subspace of K^N where N≥ 2. Let Z_K be a union of varieties defined over K such that V ⊈ Z_K. We prove the existence of a point of small height in V \ Z_K, providing an explicit upper bound on the height of such a point in terms of the height of V and the degree of hypersurface containing Z_K, where dependence on …

Integral Orthogonal Bases Of Small Height For Real Polynomial Spaces, Lenny Fukshansky

CMC Faculty Publications and Research

Let P_N(R) be the space of all real polynomials in N variables with the usual inner product < , > on it, given by integrating over the unit sphere. We start by deriving an explicit combinatorial formula for the bilinear form representing this inner product on the space of coefficient vectors of all polynomials in P_N(R) of degree ≤ M. We exhibit two applications of this formula. First, given a finite dimensional subspace V of P_N(R) defined over Q, we prove the existence of an orthogonal basis for (V, < , >), consisting of polynomials of small height …

Search Bounds For Zeros Of Polynomials Over The Algebraic Closure Of Q, Lenny Fukshansky

CMC Faculty Publications and Research

We discuss existence of explicit search bounds for zeros of polynomials with coefficients in a number field. Our main result is a theorem about the existence of polynomial zeros of small height over the field of algebraic numbers outside of unions of subspaces. All bounds on the height are explicit.

The Probability Of Relatively Prime Polynomials, Arthur T. Benjamin, Curtis D. Bennet

All HMC Faculty Publications and Research

No abstract provided in this article.

Integral Points Of Small Height Outside Of A Hypersurface, Lenny Fukshansky

CMC Faculty Publications and Research

Let F be a non-zero polynomial with integer coefficients in N variables of degree M. We prove the existence of an integral point of small height at which F does not vanish. Our basic bound depends on N and M only. We separately investigate the case when F is decomposable into a product of linear forms, and provide a more sophisticated bound. We also relate this problem to a certain extension of Siegel’s Lemma as well as to Faltings’ version of it. Finally we exhibit an application of our results to a discrete version of the Tarski plank problem.

Sums Of Kth Powers In The Ring Of Polynomials With Integer Coefficients, Ted Chinburg, Melvin Henriksen

All HMC Faculty Publications and Research

A working through of two theorems.

Suppose R is a ring with identity element and k is a positive integer. Let J(k, R) denote the subring of R generated by its kth powers. If Z denotes the ring of integers, then G(k, R) = {a ∈ Z: aR ⊂ J(k, R)} is an ideal of Z.