22

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

where Pi =

∑

{α1,αi,α|A|}⊆B⊆A

P (B/A) is the probability that αi is in the support

of the Newton Polygon. The value of Pi can be written in terms of integrals, as

shown in the following formula:

Pi =

1

0

· · ·

1

0

min

1≤jik≤t

vj

αi − αk

αj − αk

+ vk

αj − αi

αj − αk

dv1 · · · dvi · · · dvt.

The estimations

Pi ≤

1

0

· · ·

1

0

max(min(v1, . . . , vi−1), min(vi+1, . . . , vt))dv1 · · · dvi · · · dvt,

Pi ≥

1

0

· · ·

1

0

min(v1, . . . , vi,...,vt)dv1 · · · dvi · · · dvt,

show that

1

t

≤ Pi ≤

1

i

+

1

t−i+1

−

1

t

, and therefore

2 −

2

t

≤ E(A,D1,K) ≤ 2

t

i=2

1

i

≤ 2 ln(t).

Acknowledgements

We would like to thank J. Maurice Rojas and Bernd Sturmfels for several

fruitful discussions about regularity and semiregularity, and for encouraging us to

publish these results.

References

[1] M. Avenda˜ no: Descartes’ rule is exact! Journal of Algebra, vol. 324(10), pp. 2884–2892,

2010.

[2] M. Avenda˜ no, A. Ibrahim: Ultrametric root counting. Houston Journal of Mathematics,

vol. 36(4), pp. 1011–1022, 2010.

[3] M. Avenda˜ no, T. Krick: Sharp bounds for the number fo roots of univariate fewnomials.

Journal of Number Theory, vol. 131(7), pp. 1209–1228, 2011.

[4] M. Avenda˜ no, T. Krick, A. Pacetti: Newton-Hensel interpolation lifting. Foundations of

Computational Mathematics, vol. 6(1), pp. 81–120, 2006.

[5] D. Bernstein: The number of roots of a system of equations. Functional Analysis and its

Applications, vol. 9, pp. 183–185, 1975.

[6] T. Bogart, A. Jensen, D. Speyer, B. Sturmfels, R. Thomas: Computing tropical varieties.

Journal of Symbolic Computation, vol. 42(1), pp. 54–73, 2007.

[7] R. Descartes: La g´ eom´ etrie. 1637.

[8] S. Evans: The expected number of zeros of a random system of p-adic polynomials. Electron.

Comm. Probab., vol. 11, pp. 278–290, 2006.

[9] A. Khovanskii: Fewnomials. AMS Press, Providence, Rhode Island, 1991.

[10] H.W. Lenstra: On the Factorization of Lacunary Polynomials. Number Theory in Progress,

vol. 1, pp. 277-291, 1999.

[11] B. Poonen: Zeros of sparse polynomials over local fields of characteristic p. Math. Res. Lett.,

vol 5(3), pp. 273-279, 1998.

[12] J. Richter-Gebert, B. Sturmfels, T. Theobald: First steps in tropical geometry. Contemporary

Mathematics, vol. 377, pp. 289–317, 2005.

[13] A. Robert: A course in p-adic Analysis. GTM, Vol.198, Springer-verlag, 2000.

[14] J.M. Rojas: Arithmetic Multivariate Descartes’ rule. American Journal of Mathematics,

vol. 126(1), pp. 1–30, 2004.

[15] D. Speyer, B. Sturmfels: The tropical Grassmanian. Advances in Geometry, vol. 4, pp. 389–

411, 2004.

22

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

where Pi =

∑

{α1,αi,α|A|}⊆B⊆A

P (B/A) is the probability that αi is in the support

of the Newton Polygon. The value of Pi can be written in terms of integrals, as

shown in the following formula:

Pi =

1

0

· · ·

1

0

min

1≤jik≤t

vj

αi − αk

αj − αk

+ vk

αj − αi

αj − αk

dv1 · · · dvi · · · dvt.

The estimations

Pi ≤

1

0

· · ·

1

0

max(min(v1, . . . , vi−1), min(vi+1, . . . , vt))dv1 · · · dvi · · · dvt,

Pi ≥

1

0

· · ·

1

0

min(v1, . . . , vi,...,vt)dv1 · · · dvi · · · dvt,

show that

1

t

≤ Pi ≤

1

i

+

1

t−i+1

−

1

t

, and therefore

2 −

2

t

≤ E(A,D1,K) ≤ 2

t

i=2

1

i

≤ 2 ln(t).

Acknowledgements

We would like to thank J. Maurice Rojas and Bernd Sturmfels for several

fruitful discussions about regularity and semiregularity, and for encouraging us to

publish these results.

References

[1] M. Avenda˜ no: Descartes’ rule is exact! Journal of Algebra, vol. 324(10), pp. 2884–2892,

2010.

[2] M. Avenda˜ no, A. Ibrahim: Ultrametric root counting. Houston Journal of Mathematics,

vol. 36(4), pp. 1011–1022, 2010.

[3] M. Avenda˜ no, T. Krick: Sharp bounds for the number fo roots of univariate fewnomials.

Journal of Number Theory, vol. 131(7), pp. 1209–1228, 2011.

[4] M. Avenda˜ no, T. Krick, A. Pacetti: Newton-Hensel interpolation lifting. Foundations of

Computational Mathematics, vol. 6(1), pp. 81–120, 2006.

[5] D. Bernstein: The number of roots of a system of equations. Functional Analysis and its

Applications, vol. 9, pp. 183–185, 1975.

[6] T. Bogart, A. Jensen, D. Speyer, B. Sturmfels, R. Thomas: Computing tropical varieties.

Journal of Symbolic Computation, vol. 42(1), pp. 54–73, 2007.

[7] R. Descartes: La g´ eom´ etrie. 1637.

[8] S. Evans: The expected number of zeros of a random system of p-adic polynomials. Electron.

Comm. Probab., vol. 11, pp. 278–290, 2006.

[9] A. Khovanskii: Fewnomials. AMS Press, Providence, Rhode Island, 1991.

[10] H.W. Lenstra: On the Factorization of Lacunary Polynomials. Number Theory in Progress,

vol. 1, pp. 277-291, 1999.

[11] B. Poonen: Zeros of sparse polynomials over local fields of characteristic p. Math. Res. Lett.,

vol 5(3), pp. 273-279, 1998.

[12] J. Richter-Gebert, B. Sturmfels, T. Theobald: First steps in tropical geometry. Contemporary

Mathematics, vol. 377, pp. 289–317, 2005.

[13] A. Robert: A course in p-adic Analysis. GTM, Vol.198, Springer-verlag, 2000.

[14] J.M. Rojas: Arithmetic Multivariate Descartes’ rule. American Journal of Mathematics,

vol. 126(1), pp. 1–30, 2004.

[15] D. Speyer, B. Sturmfels: The tropical Grassmanian. Advances in Geometry, vol. 4, pp. 389–

411, 2004.

22