* [66] H. Wang, E. Pérez, and F. Römer.  Deep learning-based optimal spatial subsampling in ultrasound nondestructive testing.  In 2023 31st European Signal Processing Conference (EUSIPCO), pages 1863–1867, 2023.
  * [67] H. Wang, E. Pérez, and F. Römer.  Data-Driven subsampling matrices design for phased array ultrasound nondestructive testing.  In Proceedings of the 2023 IEEE International Ultrasonics Symposium (IUS-2023), Montreal, Canada, September 2023.
  * [68] H. Wang, Y. Zhou, E. Pérez, and F. Römer.  Jointly learning selection matrices for transmitters, receivers and fourier coefficients in multichannel imaging.  In Proceedings of the 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP-2024), Seoul, Korea, April 2024.
  * [69] M. T. M. Khairi, S. Ibrahim, M. A. M. Yunus, M. Faramarzi, G. P. Sean, J. Pusppanathan, and A. Abid.  Ultrasound computed tomography for material inspection: Principles, design and applications.  Measurement, 146:490–523, 2019.
  * [70] J. Gubernatis, E. Domany, J. Krumhansl, and M. Huberman.  The Born approximation in the theory of the scattering of elastic waves by flaws.  Journal of Applied Physics, 48(7):2812–2819, 1977.
  * [71] M. Zielińska and M. Rucka.  Non-Destructive Assessment of Masonry Pillars using Ultrasonic Tomography.  Materials, 11(12):2543, 2018.
  * [72] V. G. Haach and F. C. Ramirez.  Qualitative assessment of concrete by ultrasound tomography.  Construction and Building Materials, 119:61–70, 2016.
  * [73] N. Duric, P. Littrup, L. Poulo, A. Babkin, R. Pevzner, E. Holsapple, O. Rama, and C. Glide.  Detection of breast cancer with ultrasound tomography: First results with the Computed Ultrasound Risk Evaluation (CURE) prototype.  Medical physics, 34(2):773–785, 2007.
  * [74] J. Virieux, A. Asnaashari, R. Brossier, L. Métivier, A. Ribodetti, and W. Zhou.  An introduction to full waveform inversion.  In Encyclopedia of exploration geophysics, pages R1–1. Society of Exploration Geophysicists, 2017.
  * [75] L. Guasch, O. Calderón Agudo, M.-X. Tang, P. Nachev, and M. Warner.  Full-waveform inversion imaging of the human brain.  NPJ digital medicine, 3(1):28, 2020.
  * [76] G. KłosowsKi, T. Rymarczyk, K. Kania, A. Świć, and T. Cieplak.  Maintenance of industrial reactors supported by deep learning driven ultrasound tomography.  Eksploatacja i Niezawodność, 22(1):138–147, 2020.
  * [77] T. Lähivaara, L. Kärkkäinen, J. M. J. Huttunen, and J. S. Hesthaven.  Deep convolutional neural networks for estimating porous material parameters with ultrasound tomography.  The Journal of the Acoustical Society of America, 143(2):1148–1158, 2018.
  * [78] X. Long, J. Chen, W. Liu, and C. Tian.  Deep Learning Ultrasound Computed Tomography under Sparse Sampling.  IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 2023.
  * [79] O. Ronneberger, P. Fischer, and T. Brox.  U-Net: Convolutional Networks for Biomedical Image Segmentation.  In Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pages 234–241. Springer, 2015.
  * [80] M. Feigin, D. Freedman, and B. W. Anthony.  A Deep Learning Framework for Single-Sided Sound Speed Inversion in Medical Ultrasound.  IEEE Transactions on Biomedical Engineering, 67(4):1142–1151, 2019.
  * [81] M. Raissi, P. Perdikaris, and G. E. Karniadakis.  Physics-Informed Neural Networks: A Deep Learning Framework for Solving Forward and Inverse Problems Involving Nonlinear Partial Differential Equations.  Journal of Computational Physics, 378:686–707, 2019.
  * [82] B. Moseley, A. Markham, and T. Nissen-Meyer.  Solving the wave equation with physics-informed deep learning, arxiv.  arXiv preprint arXiv:2006.11894, 2020.
  * [83] M. Rasht-Behesht, C. Huber, K. Shukla, and G. E. Karniadakis.  Physics-Informed Neural Networks (PINNs) for Wave Propagation and Full Waveform Inversions.  Journal of Geophysical Research: Solid Earth, 127(5):e2021JB023120, 2022.
  * [84] K. Shukla, P. C. Di Leoni, J. Blackshire, D. Sparkman, and G. E. Karniadakis.  Physics-Informed Neural Network for Ultrasound Nondestructive Quantification of Surface Breaking Cracks.  Journal of Nondestructive Evaluation, 39:1–20, 2020.
  * [85] H. Sun, P. Ramuhalli, and R. E. Jacob.  Machine learning for ultrasonic nondestructive examination of welding defects: A systematic review.  Ultrasonics, 127:106854, 2023.
  * [86] I. Daubechies.  The wavelet transform, time-frequency localization and signal analysis.  IEEE Transactions on Information Theory, 36(5):961–1005, 1990.
  * [87] D.-Z. Dang, C.-C. Lai, Y.-Q. Ni, Q. Zhao, B. Su, and Q.-F. Zhou.  Image classification-based defect detection of railway tracks using fiber bragg grating ultrasonic sensors.  Applied Sciences, 13(1), 2023.
  * [88] Y. Jiang, H. Wang, G. Tian, Q. Yi, J. Zhao, and K. Zhen.  Fast classification for rail defect depths using a hybrid intelligent method.  Optik, 180:455–468, 2019.
  * [89] G. Lv, S. Guo, D. Chen, H. Feng, K. Zhang, Y. Liu, and W. Feng.  Laser ultrasonics and machine learning for automatic defect detection in metallic components.  NDT & E International, 133:102752, 2023.
  * [90] Y. Freund and R. E. Schapire.  A desicion-theoretic generalization of on-line learning and an application to boosting.  In P. Vitányi, editor, Computational Learning Theory, pages 23–37, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.
  * [91] T. Chen, T. He, M. Benesty, V. Khotilovich, Y. Tang, H. Cho, K. Chen, R. Mitchell, I. Cano, T. Zhou, et al.  Xgboost: extreme gradient boosting.  R package version 0.4-2, 1(4):1–4, 2015.
  * [92] M. Hearst, S. Dumais, E. Osuna, J. Platt, and B. Scholkopf.  Support vector machines.  IEEE Intelligent Systems and their Applications, 13(4):18–28, 1998.
  * [93] Y. Yan, D. Liu, B. Gao, G. Y. Tian, and Z. C. Cai.  A deep learning-based ultrasonic pattern recognition method for inspecting girth weld cracking of gas pipeline.  IEEE Sensors Journal, 20(14):7997–8006, 2020.
  * [94] Y. Chen, S. Liang, Z. Wang, H. Ma, M. Dong, D. Liu, and X. Wan.  Automatic classification of weld defects from ultrasonic signals using wpee-kpca feature extraction and an abc-svm approach.  Insight - Non-Destructive Testing and Condition Monitoring, 65(5):262–269, 2023.
  * [95] P. Pawar and R. Buktar.  Detection and classification of defects in ultrasonic testing using deep learning.  In V. K. Gunjan and J. M. Zurada, editors, Proceedings of the 2nd International Conference on Recent Trends in Machine Learning, IoT, Smart Cities and Applications, pages 1–15, Singapore, 2022. Springer Nature Singapore.
  * [96] A. Arbaoui, A. Ouahabi, S. Jacques, and M. Hamiane.  Concrete cracks detection and monitoring using deep learning-based multiresolution analysis.  Electronics, 10(15), 2021.
  * [97] A. Arbaoui, A. Ouahabi, S. Jacques, and M. Hamiane.  Wavelet-based multiresolution analysis coupled with deep learning to efficiently monitor cracks in concrete.  Frattura ed Integrità Strutturale / Fracture and Structural Integrity, 15(58):33–47, 2021.
  * [98] K. Sudheera, N. M. Nandhitha, V. B. Venkat Sai, and N. V. Kumar.  Deep learning techniques for flaw characterization in weld pieces from ultrasonic signals.  Russian Journal of Nondestructive Testing, 56:820–830, 2020.
  * [99] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [100] K. Virupakshappa and E. Oruklu.  Unsupervised machine learning for ultrasonic flaw detection using gaussian mixture modeling, k-means clustering and mean shift clustering.  In 2019 IEEE International Ultrasonics Symposium (IUS), pages 647–649, 2019.
  * [101] M. A. Oliveira, E. F. Simas Filho, M. C. Albuquerque, Y. T. Santos, I. C. da Silva, and C. T. Farias.  Ultrasound-based identification of damage in wind turbine blades using novelty detection.  Ultrasonics, 108:106166, 2020.
  * [102] J. Gilles.  Empirical wavelet transform.  IEEE Transactions on Signal Processing, 61(16):3999–4010, 2013.
  * [103] N. E. Huang, Z. Shen, S. R. Long, M. C. Wu, H. H. Shih, Q. Zheng, N.-C. Yen, C. C. Tung, and H. H. Liu.  The empirical mode decomposition and the hilbert spectrum for nonlinear and non-stationary time series analysis.  Proceedings of the Royal Society of London. Series A: mathematical, physical and engineering sciences, 454(1971):903–995, 1998.
  * [104] M. Zhang, Q. Zhang, J. Li, J. Xu, and J. Zheng.  Classification of acoustic emission signals in wood damage and fracture process based on empirical mode decomposition, discrete wavelet transform methods, and selected features.  Journal of Wood Science, 67(1):1–13, 2021.
  * [105] K. Dragomiretskiy and D. Zosso.  Variational mode decomposition.  IEEE Transactions on Signal Processing, 62(3):531–544, 2014.
  * [106] M. Mousavi and A. H. Gandomi.  Wood hole-damage detection and classification via contact ultrasonic testing.  Construction and Building Materials, 307:124999, 2021.
  * [107] H. Sun, L. Peng, S. Wang, S. Huang, and K. Qu.  Development of frequency-mixed point-focusing shear horizontal guided-wave emat for defect inspection using deep neural network.  IEEE Transactions on Instrumentation and Measurement, 70:1–14, 2021.
  * [108] S. Lohit, K. Kulkarni, and P. Turaga.  Direct inference on compressive measurements using convolutional neural networks.  In 2016 IEEE international conference on image processing (ICIP), pages 1913–1917. IEEE, 2016.
  * [109] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [110] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell.  Caffe: Convolutional architecture for fast feature embedding.  In Proceedings of the 22nd ACM international conference on Multimedia, pages 675–678, 2014.
  * [111] M. A. Davenport, M. F. Duarte, M. B. Wakin, J. N. Laska, D. Takhar, K. F. Kelly, and R. G. Baraniuk.  The smashed filter for compressive classification and target recognition.  In Computational Imaging V, volume 6498, pages 142–153. SPIE, 2007.
  * [112] Y. Guo, Z. Xiao, L. Geng, J. Wu, F. Zhang, Y. Liu, and W. Wang.  Fully convolutional neural network with gru for 3d braided composite material flaw detection.  IEEE Access, 7:151180–151188, 2019.
  * [113] J. M. Ha, H. M. Seung, and W. Choi.  Autoencoder-based detection of near-surface defects in ultrasonic testing.  Ultrasonics, 119:106637, 2022.
  * [114] R. Calderbank, S. Jafarpour, and R. Schapir.  Compressed learning : Universal sparse dimensionality reduction and learning in the measurement domain.  preprint, 2009.
  * [115] S. Cantero-Chinchilla, P. D. Wilcox, and A. J. Croxford.  Deep learning in automated ultrasonic nde – developments, axioms and opportunities.  NDT & E International, 131:102703, 2022.
  * [116] M. Aharon, M. Elad, and A. Bruckstein.  K-svd: An algorithm for designing overcomplete dictionaries for sparse representation.  IEEE Transactions on Signal Processing, 54(11):4311–4322, 2006.
  * [117] Y. Song, C. Ge, N. Song, and M. Deng.  A novel dictionary learning-based approach for ultrasound elastography denoising.  Mathematical Biosciences and Engineering, 19(11):11533–11543, 2022.
  * [118] I. Tošic, I. Jovanovic, P. Frossard, M. Vetterli, and N. Duric.  Ultrasound tomography image reconstruction with learned dictionaries.  In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2010), pages 5502–5505, Dallas, TX, USA, March 2010.
  * [119] B. A. Olshausen and D. J. Field.  Emergence of simple-cell receptive field properties by learning a sparse code for natural images.  Nature, 381(6583):607–609, 1996.
  * [120] I. Virkkunen, T. Koskinen, and O. Siljama.  Virtual round robin 2–Phased array inspection of dissimilar metal welds.  Nuclear Engineering and Design, 414:112555, 2023.
  * [121] R. J. Pyle, R. R. Hughes, A. A. S. Ali, and P. D. Wilcox.  Uncertainty quantification for deep learning in ultrasonic crack characterization.  IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 69(7):2339–2351, Jul 2022.
  * [122] T. Gantala and K. Balasubramaniam.  Automated defect recognition for welds using simulation assisted tfm imaging with artificial intelligence.  Journal of Nondestructive Evaluation, 40(1), Feb 2021.
  * [123] A. Bochkovskiy, C.-Y. Wang, and H.-Y. M. Liao.  YOLOv4: Optimal Speed and Accuracy of Object Detection.  arXiv preprint arXiv:2004.10934, 2020.
  * [124] L. Posilović, D. Medak, M. Subašić, M. Budimir, and S. Lončarić.  Generating ultrasonic images indistinguishable from real images using generative adversarial networks.  Ultrasonics, 119:106610, Feb 2022.
  * [125] P. Isola, J.-Y. Zhu, T. Zhou, and A. A. Efros.  Image-to-Image Translation with Conditional Adversarial Networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1125–1134, 2017.
  * [126] J. Redmon and A. Farhadi.  YOLOv3: An Incremental Improvement.  arXiv preprint arXiv:1804.02767, 2018.
  * [127] T. Park, M.-Y. Liu, T.-C. Wang, and J.-Y. Zhu.  Semantic Image Synthesis with Spatially-Adaptive Normalization.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2337–2346, 2019.
  * [128] T.-C. Wang, M.-Y. Liu, J.-Y. Zhu, A. Tao, J. Kautz, and B. Catanzaro.  High-Resolution Image Synthesis and Semantic Manipulation with Conditional GANs.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8798–8807, 2018.
  * [129] J. Singh, K. Tant, A. Curtis, and A. Mulholland.  Real-time super-resolution mapping of locally anisotropic grain orientations for ultrasonic non-destructive evaluation of crystalline material.  Neural Computing and Applications, 34(6):4993–5010, Nov 2021.
  * [130] B. Ni and H. Gao.  A deep learning approach to the inverse problem of modulus identification in elasticity.  MRS Bulletin, 46(1):19–25, Jan 2021.
  * [131] M. Mirza and S. Osindero.  Conditional generative adversarial nets.  arXiv preprint arXiv:1411.1784, 2014.
  * [132] C. Song, T. Alkhalifah, and U. B. Waheed.  A versatile framework to solve the helmholtz equation using physics-informed neural networks.  Geophysical Journal International, 228(3):1750–1762, 10 2021.
  * [133] C. Offen and S. Ober-Blöbaum.  Learning discrete lagrangians for variational PDEs from data and detection of travelling waves.  In Lecture Notes in Computer Science, pages 569–579. Springer Nature Switzerland, 2023.
  * [134] G. E. Karniadakis, I. G. Kevrekidis, L. Lu, P. Perdikaris, S. Wang, and L. Yang.  Physics-informed machine learning.  Nature Review Physics, 3:422–440, 2021.
  * [135] D. P. Almond and S. Lau.  Defect sizing by transient thermography. i. an analytical treatment.  Journal of Physics D: Applied Physics, 27(5):1063, 1994.
  * [136] X. Maldague and S. Marinetti.  Pulse phase infrared thermography.  Journal of applied physics, 79(5):2694–2698, 1996.
  * [137] U. Netzelmann and D. Müller.  Modified pulse-phase thermography algorithms for improved contrast-to-noise ratio from pulse-excited thermographic sequences.  NDT & E International, 116:102325, 2020.
  * [138] G. Poelman, S. Hedayatrasa, J. Segers, W. Van Paepegem, and M. Kersemans.  Adaptive spectral band integration in flash thermography: Enhanced defect detectability and quantification in composites.  Composites Part B: Engineering, 202:108305, 2020.
  * [139] N. Rajic.  Principal component thermography for flaw contrast enhancement and flaw depth characterisation in composite structures.  Composite Structures, 58(4):521–528, 2002.
  * [140] B. Milovanović, M. Gaši, and S. Gumbarević.  Principal component thermography for defect detection in concrete.  Sensors, 20(14):3891, 2020.
  * [141] M. Omar, R. Parvataneni, and Y. Zhou.  A combined approach of self-referencing and principle component thermography for transient, steady, and selective heating scenarios.  Infrared physics & technology, 53(5):358–362, 2010.
  * [142] Y. Liu, F. Wang, Z. Jiang, S. Sfarra, K. Liu, and Y. Yao.  Generative deep learning-based thermographic inspection of artwork.  Sensors, 23(14):6362, 2023.
  * [143] H. Zhong, S. Yu, H. Trinh, Y. Lv, R. Yuan, and Y. Wang.  Fine-tuning transfer learning based on dcgan integrated with self-attention and spectral normalization for bearing fault diagnosis.  Measurement, 210:112421, 2023.
  * [144] S. M. Shepard.  Advances in thermographic ndt.  In Infrared Technology and Applications XXIX, volume 5074, pages 882–887. SPIE, 2003.
  * [145] J. Roche, F. Leroy, and D. Balageas.  Images of thermographic signal reconstruction coefficients: A simple way for rapid and efficient detection of discontinuities.  Materials evaluation, 72(1):73–82, 2014.
  * [146] A. Schager, G. Zauner, G. Mayr, and P. Burgholzer.  Extension of the thermographic signal reconstruction technique for an automated segmentation and depth estimation of subsurface defects.  Journal of Imaging, 6(9):96, 2020.
  * [147] Q. Feng, B. Gao, P. Lu, W. L. Woo, Y. Yang, Y. Fan, X. Qiu, and L. Gu.  Automatic seeded region growing for thermography debonding detection of cfrp.  Ndt & E International, 99:36–49, 2018.
  * [148] A. Ratsakou, A. Skarlatos, C. Reboud, and D. Lesselier.  Shape reconstruction of delamination defects using thermographic infrared signals based on an enhanced canny approach.  Infrared Physics & Technology, 111:103527, 2020.
  * [149] M.-M. Groz, E. Abisset-Chavanne, A. Meziane, A. Sommier, and C. Pradère.  Three-dimensional reconstruction of thermal volumetric sources from surface temperature fields measured by infrared thermography.  Applied Sciences, 9(24):5464, 2019.
  * [150] P. Burgholzer, M. Thor, J. Gruber, and G. Mayr.  Three-dimensional thermographic imaging using a virtual wave concept.  Journal of Applied Physics, 121(10), 2017.
  * [151] P. Kovács, B. Lehner, G. Thummerer, G. Mayr, P. Burgholzer, and M. Huemer.  Deep learning approaches for thermographic imaging.  Journal of Applied Physics, 128, 10 2020.
  * [152] D. Gillsjö, G. Flood, and K. Åström.  Semantic room wireframe detection from a single view.  In 2022 26th International Conference on Pattern Recognition (ICPR), pages 1886–1893. IEEE, 2022.
  * [153] Y. Zhou, A. Osman, M. Willms, A. Kunz, S. Philipp, J. Blatt, and S. Eul.  Semantic wireframe detection.  In DGZfP Jahrestagung 2023, Friedrichshafen, 2023.
  * [154] S. Guan, N. Kamona, and M. Loew.  Segmentation of thermal breast images using convolutional and deconvolutional neural networks.  In 2018 IEEE Applied Imagery Pattern Recognition Workshop (AIPR), Washington DC, USA, 10 2018.
  * [155] O. Pedrayes, D. Lema, R. Usamentiaga, V. Pablo, and F. D. Garcia.  Semantic segmentation for non-destructive testing with step-heating thermography for composite laminates.  Measurement, 200:111653, 07 2022.
  * [156] D. Müller, U. Netzelmann, and B. Valeske.  Defect shape detection and defect reconstruction in active thermography by means of two-dimensional convolutional neural network as well as spatiotemporal convolutional lstm network.  Quantitative InfraRed Thermography Journal, 19:1–19, 09 2020.
  * [157] A. A. R. M. A. Ebayyeh and A. Mousavi.  A review and analysis of automatic optical inspection and quality monitoring methods in electronics industry.  IEEE Access, 8:183192–183271, 2020.
  * [158] C. Demant, B. Streicher-Abel, and A. Springhoff.  Industrielle Bildverarbeitung: Wie optische Qualitätskontrolle wirklich funktioniert.  Springer Berlin Heidelberg, 2011.
  * [159] P. Bharati and A. Pramanik.  Deep learning techniques—r-cnn to mask r-cnn: a survey.  Computational Intelligence in Pattern Recognition: Proceedings of CIPR 2019, pages 657–668, 2020.
  * [160] S. Ren, K. He, R. Girshick, and J. Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks, 2016.
  * [161] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition, 2015.
  * [162] M. Everingham, S. M. A. Eslami, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes challenge: A retrospective.  International Journal of Computer Vision, 111(1):98–136, January 2015.
  * [163] T.-Y. Lin, M. Maire, S. Belongie, L. Bourdev, R. Girshick, J. Hays, P. Perona, D. Ramanan, C. L. Zitnick, and P. Dollár.  Microsoft coco: Common objects in context, 2015.
  * [164] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg.  Ssd: Single shot multibox detector.  In Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part I 14, pages 21–37. Springer, 2016.
  * [165] P. Jiang, D. Ergu, F. Liu, Y. Cai, and B. Ma.  A review of yolo algorithm developments.  Procedia Computer Science, 199:1066–1073, 2022.
  * [166] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi.  You only look once: Unified, real-time object detection, 2016.
  * [167] G. Jocher, A. Chaurasia, and J. Qiu.  Yolo by ultralytics.  https://github.com/ultralytics/, 2023.  Accessed on 12 January 2023.
  * [168] K. He, G. Gkioxari, P. Dollár, and R. Girshick.  Mask r-cnn, 2018.
  * [169] E. Shelhamer, J. Long, and T. Darrell.  Fully convolutional networks for semantic segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(4):640–651, 2017.
  * [170] I. Katsamenis, E. Protopapadakis, A. Doulamis, N. Doulamis, and A. Voulodimos.  Pixel-level corrosion detection on metal constructions by fusion of deep learning semantic and contour segmentation, 2020.
  * [171] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna.  Rethinking the inception architecture for computer vision, 2015.
  * [172] C. Wang, F. Shi, M. Zhao, J. Ao, C. Jia, and S. Chen.  Convolutional Neural Network-Based Terahertz Spectral Classification of Liquid Contraband for Security Inspection.  IEEE Sensors Journal, 21(17):18955–18963, 2021.
  * [173] Z. Xiao, K.-Y. Song, and M. M. Gupta.  Development of a CNN edge detection model of noised X-ray images for enhanced performance of non-destructive testing.  Measurement, 174:109012, 2021.
  * [174] S. S. A. Zaidi, M. S. Ansari, A. Aslam, N. Kanwal, M. Asghar, and B. Lee.  A survey of modern deep learning based object detection models.  Digital Signal Processing, 126:103514, 2022.
  * [175] T. Van De Looverbosch, B. Vandenbussche, P. Verboven, and B. Nicolaï.  Nondestructive high-throughput sugar beet fruit analysis using X-ray CT and deep learning.  Computers and Electronics in Agriculture, 200:107228, 2022.
  * [176] B. Hena, Z. Wei, C. I. Castanedo, and X. Maldague.  Deep Learning Neural Network Performance on NDT Digital X-ray Radiography Images: Analyzing the Impact of Image Quality Parameters—An Experimental Study.  Sensors, 23(9):4324, 2023.
  * [177] Y. Jiang, G. Li, H. Ge, F. Wang, L. Li, X. Chen, M. Lu, and Y. Zhang.  Machine Learning and Application in Terahertz Technology: A Review on Achievements and Future Challenges.  IEEE Access, 10:53761–53776, 2022.
  * [178] S. Helal, H. Sarieddeen, H. Dahrouj, T. Y. Al-Naffouri, and M.-S. Alouini.  Signal Processing and Machine Learning Techniques for Terahertz Sensing: An overview.  IEEE Signal Processing Magazine, 39(5):42–62, 2022.
  * [179] A. Mamistvalov, A. Amar, N. Kessler, and Y. C. Eldar.  Deep-learning based adaptive ultrasound imaging from sub-nyquist channel data.  IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 69(5):1638–1648, 2022.
  * [180] D. Perdios, M. Vonlanthen, F. Martinez, M. Arditi, and J.-P. Thiran.  Cnn-based image reconstruction method for ultrafast ultrasound imaging.  IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, 69(4):1154–1168, 2021.
  * [181] C. J. Schuler, M. Hirsch, S. Harmeling, and B. Schölkopf.  Learning to Deblur.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(7):1439–1451, 2016.
  * [182] D. L. Balageas, J.-M. Roche, F.-H. Leroy, W.-M. Liu, and A. M. Gorbach.  The thermographic signal reconstruction method: A powerful tool for the enhancement of transient thermographic images.  Biocybernetics and biomedical engineering, 35(1):1–9, 2015.
  * [183] G. Batchuluun, Y. Lee, D. Nguyen, T. Pham, and K. Park.  Thermal image reconstruction using deep learning.  IEEE Access, PP:1–1, 07 2020.
  * [184] P. Sahoo, S. Soltani, and A. Wong.  A survey of thresholding techniques.  Computer Vision, Graphics, and Image Processing, 41(2):233–260, 1988.


# An improved bound on sums of square roots via the subspace theorem

Friedrich Eisenbrand EPFL, Switzerland<EMAIL_ADDRESS>Matthieu
Haeberle EPFL, Switzerland<EMAIL_ADDRESS>Neta Singer EPFL,
Switzerland<EMAIL_ADDRESS>
###### Abstract

The _sum of square roots_ is as follows: Given
$x_{1},\dots,x_{n}\in\mathbb{Z}$ and $a_{1},\dots,a_{n}\in\mathbb{N}$ decide
whether $E=\sum_{i=1}^{n}x_{i}\sqrt{a_{i}}\geq 0$. It is a prominent open
problem (Problem 33 of the _Open Problems Project_), whether this can be
decided in polynomial time. The state-of-the-art methods rely on separation
bounds, which are lower bounds on the minimum nonzero absolute value of $E$.
The current best bound shows that
$|E|\geq\left(n\cdot\max_{i}(|x_{i}|\cdot\sqrt{a_{i}})\right)^{-2^{n}}$, which
is doubly exponentially small.

We provide a new bound of the form
$|E|\geq\gamma\cdot(n\cdot\max_{i}|x_{i}|)^{-2n}$ where $\gamma$ is a constant
depending on $a_{1},\dots,a_{n}$. This is singly exponential in $n$ for fixed
$a_{1},\dots,a_{n}$. The constant $\gamma$ is not explicit and stems from the
_subspace theorem_ , a deep result in the _geometry of numbers_.

##  1 Introduction

Several geometric optimization problems such as _euclidean traveling salesman_
or _euclidean shortest path_ , rely on comparisons of _sums of square roots_ ,
which is a decision problem as follows. Given integers
$x_{1},\dots,x_{n}\in\mathbb{Z}$ and positive integers
$a_{1},\dots,a_{n}\in\mathbb{N}$ decide whether

$E=\sum_{i=1}^{n}x_{i}\sqrt{a_{i}}\geq 0.$ (1)

While the decision problem (1) is easy to state, it is not known to be
decidable in polynomial time on a Turing machine, nor is it known to be NP
[13], see also [19, 10, 1]. The best known complexity class containing the
decision problem (1) is PSPACE. This follows by modeling the decision as a
problem in the _existential theory of the reals_ for which a PSPACE-algorithm
exists [6, 21]. The _zero test_ (when $\geq 0$ is replaced by $=0$) can be
decided in polynomial time with an algorithm of Blömer [3, 4].

The state-of-the-art method to decide (1) is based on _separation bounds_ ,
see, e.g. [18]. Separation bounds are lower bounds on the absolute value of
$E$, defined in (1), when it is nonzero. The best known bound in our setting
is by Burnikel et al. [5]. The bound follows from the fact that the product of
the _conjugates_ , see, e.g. [16], of $E$ is an integer. Each conjugate of $E$
is of the form

$\sum_{i=1}^{n}y_{i}\cdot x_{i}\sqrt{a_{i}},\quad y\in\\{\pm 1\\}^{n},$

of absolute value bounded by $n\max\limits_{i}(|x_{i}|\sqrt{a_{i}})$. This
implies that

$|E|\geq\left(n\max_{i}\left(|x_{i}|\sqrt{a_{i}}\right)\right)^{-(2^{n}-1)}$
(2)

whenever $E\not=0$. If follows that (1) can be decided with an approximation
of the numbers $x_{i}\sqrt{a_{i}}$ in which
$\mathcal{O}\left[2^{n}\log\left(n\max\limits_{i}\left(|x_{i}|\sqrt{a_{i}}\right)\right)\right]$
bits of the respective fractional parts are correct. This bound is exponential
in $n$.

On the other hand, there is no empirical evidence [8] that the reciprocal
$1/|E|$ can be doubly exponential in $n$. The best empirical lower bounds [20]
observed for $1/|E|$ are of the form $\left(\max_{i}a_{i}\right)^{\Omega(n)}$.
The question of whether singly-exponential separation bounds for $|E|$ exist,
is a highly visible open problem in computing [19], see also [9, Problem 33].

### Contribution of this paper

Our main result is a new separation bound for $|E|$ that shows single-
exponential dependence on $n$ if $a_{1},\dots,a_{n}$ are fixed. More
precisely, we show the following.

  1. i)

If $E\not=0$, then

$|E|\geq\left(\frac{1}{n\cdot\|x\|_{\infty}}\right)^{2n}\cdot\gamma,\,\begin{aligned}
&\textrm{ where $\gamma\in\mathbb{R}_{+}$ is a constant depending on
$\sqrt{a_{1}},\dots,\sqrt{a_{n}}$}.\end{aligned}$

Compared to the bound (2) of Burnikel et al. this decreases the dependence on
$\|x\|_{\infty}$ from doubly exponential in $n$ to exponential. The new bound
is obtained by applying tools and concepts from the _geometry of numbers_ such
as _lattices_ , _Minkowski’s first and second theorem_ , and Schmidt’s [22]
celebrated _subspace theorem_. This bound is asymptotically (almost) tight in
the following sense.

  1. ii)

For each $L\in\mathbb{N}_{\geq 2}$ there exists $x\in\mathbb{Z}^{n}$,
$x\not=0$ with $\|x\|_{\infty}\leq L$ with

$0<|E|\leq\frac{n\max_{i}\sqrt{a_{i}}}{L^{n-1}}.$

This bound follows form the pigeon-hole principle, similar to its application
to the _number-balancing problem_ [15, 14].

######  Remark 1.

The format of Problem 33 in [9] differs slightly from the problem description
(1) in this paper. Using our notation, Problem 33 requires $n$ to be even and
$x_{i}\in\\{\pm 1\\}$ for $i=1,\dots,n$. Furthermore exactly half of the
$x_{i}$ are positive one. However, the question whether the logarithm of the
reciprocal of the best separation bound is exponential or sub-exponential in
$n$ is equivalent in both settings. The problem (1) can be reformulated in the
format of Problem 33 by replacing $x_{i}\sqrt{a_{i}}$ with $x_{i}\not=0$ with
$(x_{i}/|x_{i}|)\sqrt{x_{i}^{2}a_{i}}$ and doubling $n$ if necessary.

#### Simplifying assumptions

Before we develop the connection of separation bounds for (1) to the geometry
of numbers, we justify simplifying assumptions on the input of (1). If some
$a_{i}$ is divisible by a square $y^{2}$ with
$y\in\mathbb{N}\setminus\\{0,1\\}$, then $a_{i}$ can be replaced by
$a_{i}/y^{2}$ as long as $x_{i}$ is replaced by $x_{i}\cdot y$. Furthermore,
if $a_{i}=a_{j}$ for $i\not=j$, then we can delete $a_{j}$ and replace $x_{i}$
with $x_{i}+x_{j}$, thereby reducing the dimension $n$ that appears in the
exponent of our bound. We can therefore assume, without loss of generality,
that each $a_{i}\in\mathbb{N}$ is _square-free_ and that the $a_{i}$ are
_distinct_. We recall the following fact, see [2].

######  Theorem 2.

Let $a_{1},\dots,a_{n}\in\mathbb{N}_{+}$ be distinct square-free integers. The
set

$\left\\{\sqrt{a_{1}},\dots,\sqrt{a_{n}}\right\\}$

is linearly independent over the rational numbers $\mathbb{Q}$.

##  2 Lattices and separation bounds

Let $A\in\mathbb{R}^{n\times n}$ be a matrix of full rank. The set
$\Lambda(A)=\\{Ax\colon x\in\mathbb{Z}^{n}\\}$ is the _lattice_ generated by
the _(lattice) basis_ $A$. If $A\in\mathbb{Q}^{n\times n}$ is rational, then
the lattice $\Lambda(A)$ is rational. A _shortest vector_ w.r.t. a norm
$\|\cdot\|$ of a lattice $\Lambda\subseteq\mathbb{R}^{n}$ is a nonzero
$v\in\Lambda$ of minimal norm. Lattices have been used in the context of
computing separation bounds by Cheng et al. [8]. Here, the main idea is to
consider the lattice generated by the basis

$\begin{pmatrix}N&-N\sqrt{a_{1}}&\cdots&-N\sqrt{a_{n}}\\\ &1&&\\\ &&\ddots&\\\
&&&1\end{pmatrix}$ (3)

where $N\in\mathbb{N}_{+}$ is a positive integer. Suppose one is interested in
the minimum absolute value of $E$ in (1) where the $x_{i}$ are bounded by one
in absolute value. If the length of the shortest vector w.r.t. $\ell_{2}$ is
larger than $\sqrt{n+1}$, then $1/N$ is a lower bound on $E$ in that case.
Using algorithms for computing or approximating shortest vectors in the
$\ell_{2}$-norm [17, 24] can then be used to find the smallest such $N$. The
approach of Cheng et al. [8] is suitable for computing good lower bounds for
large instances of the sum-of-square-roots problem.

Our approach is based on the dual of the lattice generated by (3). Recall that
the _dual_ lattice of $\Lambda\subseteq\mathbb{R}^{n}$ is the lattice

$\Lambda^{*}=\\{y\in\mathbb{R}^{n}\colon y^{T}v\in\mathbb{Z}\text{ for each
}v\in\Lambda\\}.$

If $\Lambda$ is generated by $A\in\mathbb{R}^{n\times n}$, then $\Lambda^{*}$
is generated by $A^{-T}$, see, e.g. [7]. Let $Q=N^{1/(n+1)}$ and denote
$\beta_{i}=\sqrt{a_{i}}$ for $i=1,\dots,n$. The dual of the lattice generated
by (3) is thus generated by the basis

$B=\begin{pmatrix}1/Q^{n+1}&&&\\\ \beta_{1}&1&&\\\ \vdots&&\ddots&\\\
\beta_{n}&&&1\end{pmatrix}$ (4)

Let $\|\cdot\|$ be a norm and $i\in\\{1,\dots,n\\}$. The _$i$ -th successive
minimum_ of $\Lambda$ is the smallest radius $R>0$ such that
$\\{x\in\mathbb{R}^{n}\colon\|x\|\leq R\\}$ contains $i$ linearly independent
lattice vectors. $i$-th successive minimum is denoted by $\lambda_{i}$. In the
following, we will restrict our attention to the successive minima w.r.t. the
$\ell_{\infty}$-norm.

The absolute value of the determinant of any basis of a lattice
$\Lambda\subseteq\mathbb{R}^{n}$ is an invariant of the lattice. It is called
the _lattice determinant_ and is denoted by $\det(\Lambda)$. The following is
referred to as Minkowski’s second theorem. We state it for the
$\ell_{\infty}$-norm, see [7].

######  Theorem 3 (Minkowski’s theorem for $\ell_{\infty}$).

Let $\Lambda\subseteq\mathbb{R}^{n}$ be a lattice. One has

$\lambda_{1}\cdots\lambda_{n}\leq\det(\Lambda),$ (5)

where the successive minima $\lambda_{i}$ are with respect to the
$\ell_{\infty}$-norm. In particular, one has

$\lambda_{1}\leq\det(\Lambda)^{1/n}.$

We now develop the connection between separation bounds for (1) and the theory
described so far. Observe that the determinant of the lattice generated by the
basis $B$ in (4) is $1/Q^{n+1}$ and that the dimension is $n+1$. Theorem 3
implies that $\Lambda(B)$ contains a nonzero lattice vector $v$ with
$\|v\|_{\infty}\leq 1/Q$. If this bound is almost tight, then the value of $Q$
carries over to a separation bound for $E$ in (1). This is our next theorem.

######  Theorem 4.

Consider $E=\sum_{i=1}^{n}x_{i}\sqrt{a_{i}}$ with
$a_{1},\dots,a_{n}\in\mathbb{N}$ and
$x=(x_{1},\dots,x_{n})\leavevmode\nobreak\ \in\leavevmode\nobreak\
\mathbb{Z}^{n}\leavevmode\nobreak\ \setminus\leavevmode\nobreak\ \\{0\\}$ and
let $\Lambda(B)$ be the lattice generated by $B$ in (4).

If $Q\geq\left(2n\|x\|_{\infty}\right)^{3/2}$ and if $\lambda_{1}\geq
1/Q^{1+\frac{1}{3n}}$, then

$|E|\geq\frac{1}{Q^{n+1}}.$ (6)

###### Proof.

Minkowski’s second theorem gives the bound

$\displaystyle\prod_{i=1}^{n+1}\lambda_{i}\leq\frac{1}{Q^{n+1}}.$ (7)

Since $\lambda_{1}\geq 1/Q^{1+\frac{1}{3n}}$ one has

$\lambda_{i}\leq\frac{1}{Q^{2/3}}\text{ for each }i\in\\{1,\dots,n+1\\}.$

The successive minima are attained at $n+1$ linearly independent lattice
vectors. Therefore, one of the successive minima is attained at a lattice
vector

$v=B\cdot\begin{pmatrix}q\\\ -p\end{pmatrix}$

with $q\in\mathbb{N}$ and $p=(p_{1},\dots,p_{n})^{T}\in\mathbb{Z}^{n}$ such
that $p^{T}x\not=0$. Since $p^{T}x\in\mathbb{Z}$, one has

$|p^{T}x|\geq 1.$ (8)

The condition $\|v\|_{\infty}\leq 1/Q^{2/3}$ implies that

$\displaystyle|q\cdot\beta_{i}-p_{i}|\leq\frac{1}{Q^{2/3}}\leq\frac{1}{2n\|x\|_{\infty}}\text{
for each }i\in\\{1,\dots,n+1\\}.$

By the triangle inequality,

$|q\beta^{T}x-p^{T}x|\leq\frac{1}{2}$

which, together with $|p^{T}x|\geq 1$ implies that

$|\beta^{T}x|\geq\frac{1}{2q}.$ (9)

On the other hand, $\|v\|_{\infty}\leq 1/Q^{2/3}$ implies that $q\leq
Q^{n+\frac{1}{3}}$. The claim follows with (9) and since $2\cdot
Q^{n+\frac{1}{3}}\leq Q^{n+1}$ for
$Q\geq\left(2n\|x\|_{\infty}\right)^{3/2}\geq 2^{3/2}$. ∎

######  Remark 5.

This proof generalizes the main idea of a technique of Frank and Tardos [12].
An integer vector $p\in\mathbb{Z}^{n}$ stemming from
$(q,p^{T})\in\mathbb{N}\times\mathbb{Z}^{n}$ that is a sufficiently good
simultaneous approximation to a real vector $\beta\in\mathbb{R}^{n}$,
separates the same set of integer points $y$ with bounded infinity norm, as
long as $p^{T}y\not=0$. We use this principle in (8), when all successive
minima are sufficiently good approximations.

### Using the subspace theorem

We consider again a lattice vector in $v\in\Lambda(B)$

$v=\begin{pmatrix}1/Q^{n+1}&&&\\\ \beta_{1}&1&&\\\ \vdots&&\ddots&\\\
\beta_{n}&&&1\end{pmatrix}\cdot\begin{pmatrix}q\\\ -p_{1}\\\ \vdots\\\
-p_{n}\\\ \end{pmatrix}$ (10)

with $q\in\mathbb{N}$ and $p=(p_{1},\dots,p_{n})^{T}\in\mathbb{Z}^{n}$.
Minkowski’s bound $\lambda_{1}\leq 1/Q$ implies the theorem of Dirichlet on
_simultaneous Diophantine approximation_ , see [23].

######  Theorem 6 (Dirichlet’s Theorem).

Given $\beta_{1},\dots,\beta_{n}\in\mathbb{R}$ and $Q\in\mathbb{N}_{+}$, there
exist integers $q,p_{1},\dots,p_{n}\in\mathbb{Z}$ with

  1. i)

$1\leq q\leq Q^{n}$ and

  2. ii)

$|q\beta_{i}-p_{i}|\leq 1/Q$ for $i=1,\dots,n$.

The _subspace theorem_ of Wolfgang Schmidt [22] implies a lower bound that is
almost tight.

######  Theorem 7 (Theorem 1B in [23]).

Let $\beta_{1},\dots,\beta_{n}\in\mathbb{R}$ be real algebraic numbers such
that $\\{1,\beta_{1},\dots,\beta_{n}\\}$ is linearly independent over
$\mathbb{Q}$ and let $\delta>0$. There are only finitely many positive
integers $q\in\mathbb{N}_{+}$ such that

$q^{1+\delta}\operatorname{dist}_{\mathbb{Z}}(q\cdot\beta_{1})\cdots\operatorname{dist}_{\mathbb{Z}}(q\cdot\beta_{n})<1.$

Here $\operatorname{dist}_{\mathbb{Z}}(x)$ is the distance of the real number
$x\in\mathbb{R}$ to the integers. It remains to show that there exists a good
$Q$ satisfying the conditions of Theorem 4, which together with Theorem 7 will
prove our main result.

######  Theorem 8.

Consider $E=\sum_{i=1}^{n}x_{i}\sqrt{a_{i}}$ with
$a_{1},\dots,a_{n}\in\mathbb{N}$ and
$x=(x_{1},\dots,x_{n})\leavevmode\nobreak\ \in\leavevmode\nobreak\
\mathbb{Z}^{n}\leavevmode\nobreak\ \setminus\leavevmode\nobreak\ \\{0\\}$.
There exists a constant $\gamma\in\mathbb{R}$ depending on $a_{1},\dots,a_{n}$
such that $E\not=0$ implies

$|E|\geq\left(\frac{1}{n\cdot\|x\|_{\infty}}\right)^{2n}\cdot\gamma.$ (11)

###### Proof.

Following the arguments in Section 1 we can assume that the $a_{i}$ are
distinct square-free integers. And assume for now that all $a_{i}$ are
different from one. This implies that the set

$\left\\{1,\beta_{1}=\sqrt{a_{1}},\dots,\beta_{n}=\sqrt{a_{n}}\right\\}$

is linearly independent over $\mathbb{Q}$. It remains to show that there
exists some $Q_{0}\in\mathbb{N}_{+}$ such that the first successive minimum
$\lambda_{1}$ of the lattice $\Lambda(B)$ verifies $\lambda_{1}\geq
1/Q^{1+\frac{1}{3n}}$ for all $Q\geq Q_{0}$. The assertion then follows with
Theorem 4 applied to $Q=(Q_{0}\cdot\left(2n\|x\|_{\infty}\right)^{3/2})$. To
this end, let $\delta=\frac{1}{3n}$ and suppose to the contrary that the first
successive minimum of $\Lambda(B)$ satisfies

$\lambda_{1}\leq\frac{1}{Q^{1+\delta}}.$

This means that there exists a $q\in\mathbb{N}_{+}$ with

  1. i)

$q\leq Q^{n-\delta}$ and

  2. ii)

$\operatorname{dist}_{\mathbb{Z}}(q\beta_{i})\leq{1}/{Q^{1+\delta}}$ for each
$i\in\\{1,\dots,n\\}$.

The condition i) implies that

$q^{1+\delta}\leq Q^{(n-\delta)(1+\delta)}<Q^{n(1+\delta)}.$

Together with ii) this implies that

$q^{1+\delta}\operatorname{dist}_{\mathbb{Z}}(q\beta_{1})\cdots\operatorname{dist}_{\mathbb{Z}}(q\beta_{n})<1.$
(12)

By theorem 7, the number of integral $q$ verifying (12) is finite.
Furthermore, given that $\beta_{1}$ is a square root of an integer, we have
that

$\frac{1}{q\cdot(2\beta_{1}+1)}\leq\operatorname{dist}_{\mathbb{Z}}(q\beta_{1})\leq\frac{1}{Q^{1+\delta}}.$

Therefore, $q$ is bounded from below by an increasing function of $Q$. As
there are finitely many $q$ verifying (12), there are also finitely many $Q$
for which $\lambda_{1}\leq\frac{1}{Q^{1+\delta}}$. Therefore, there exists a
bound $Q_{0}$ such that for all $Q\geq Q_{0}$ the successive minimum
$\lambda_{1}$ of $\Lambda(B)$ satisfies $\lambda_{1}\geq
1/Q^{1+\frac{1}{3n}}$.

We now also consider the case $a_{1}$ is equal to $1$. In this case,
$\beta_{1}=1$ and the lattice basis $B$ is given by

$B=\begin{pmatrix}1/Q^{n+1}&&&&\\\ 1&1&&&\\\ \beta_{2}&&1&&\\\
\vdots&&&\ddots&\\\ \beta_{n}&&&&1\end{pmatrix}$

It is easy to see that the first successive minimum of $\Lambda(B)$ remains
the same upon deletion of the second row and column. Denote this updated basis
by $B^{\prime}\in\mathbb{R}^{n\times n}$. With exactly the same argument as
above, it follows that there exists a $Q_{0}$ such that, for all $Q\geq Q_{0}$
one has $\lambda_{1}$ of $\Lambda(B^{\prime})$ satisfies $\lambda_{1}\geq
1/Q^{1+\frac{1}{3n}}$.

Finally, by choosing $Q=(Q_{0}\cdot\left(2n\|x\|_{\infty}\right)^{3/2})$, we
obtain the lower bound dependent on $Q_{0}$ and a single exponential in
$n\cdot\|x\|_{\infty}$. Moreover, $Q_{0}$ depends only on the bound for the
finitely many $q$ verifying the statement of Theorem 7. This means that
$Q_{0}$ is a constant depending only on $a_{1},\dots,a_{n}$.

∎

######  Remark 9.

The exponent $2n$ of equation (11) can be decreased to any $n+\epsilon$, with
$\epsilon>0$ using a suitable $\delta$ when applying Theorem 7. Note that this
would affect the constant $\gamma$ by making it dependent on $\epsilon$.

##  3 An upper bound via number balancing

We now show asymptotic (almost) tightness of the bound on $|E|$ when
$a_{1},\dots,a_{n}$ are fixed and distinct square-free positive integers.
Since $\sqrt{a_{1}},\cdots,\sqrt{a_{n}}$ are linearly independent over
$\mathbb{Q}$, $E$ is nonzero whenever $x\in\mathbb{Z}^{n}$ is not equal to
zero. We show that there exist solutions asymptotically (almost) tight in
$\|x\|_{\infty}$ via the pigeon-hole principle, as it is used in the _number
balancing problem_ [15, 14].

######  Theorem 10.

Let $L\geq 2$. There exists a nonzero $x\in\mathbb{Z}^{n}$ with
$\|x\|_{\infty}\leq L$ such that

$|E|\leq\frac{n\max_{i}\sqrt{a_{i}}}{L^{n-1}}.$

###### Proof.

Let $\beta=(\sqrt{a_{1}},\dots,\sqrt{a_{n}})\in\mathbb{R}^{n}$. The number of
vectors $y\in\mathbb{Z}^{n}$ such that $\|y\|_{\infty}\leq L/2$ holds is at
most $L^{n}$. On the other hand one always has

$|y^{T}\beta|\leq\frac{nL}{2}\max_{i}\sqrt{a_{i}}$

for such vectors $y$. By the pigeon-hole principle, there exist $y_{1}\neq
y_{2}\in\mathbb{Z}^{n}$ of infinity norms at most $L/2$ such that their
corresponding values are close:

$|y_{1}^{T}\beta-
y_{2}^{T}\beta|\leq\frac{2nL}{2(L^{n}-1)}\max_{i}\sqrt{a_{i}}.$

The difference $x=y_{1}-y_{2}$ hence verifies $\|x\|_{\infty}\leq L$ and the
required bound. ∎

##  4 Discussion

The subspace theorem (Theorem 7) does not provide explicit bounds on the
number of solutions $q\in\mathbb{N}_{+}$. The existing _quantitative_ versions
of the subspace theorem, see, e.g. [11], do not provide such bounds either.
This is still the case when all algebraic numbers are square roots of
integers. An explicit bound on the number of solutions would immediately apply
to a separation bound for the sum of square roots.

In light of the relationship of the subspace theorem and separation bounds
that we describe in this paper, it is an interesting open problem to find
explicit upper and lower bounds on the number of solutions
$q\in\mathbb{N}_{+}$ satisfying the equations of Theorem 7 for
$\beta_{i}=\sqrt{a_{i}}$ and $\delta=1/\operatorname{poly}(n)$.

## References

  * [1] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, 2009.
  * [2] Abram S Besicovitch.  On the linear independence of fractional powers of integers.  Journal of the London Mathematical Society, 1(1):3–6, 1940.
  * [3] Johannes Blömer.  Computing sums of radicals in polynomial time.  In Proceedings of the 32nd annual symposium on Foundations of computer science, pages 670–677, 1991.
  * [4] Johannes Blömer.  A probabilistic zero-test for expressions involving roots of rational numbers.  In Algorithms—ESA’98: 6th Annual European Symposium Venice, Italy, August 24–26, 1998 Proceedings 6, pages 151–162. Springer, 1998.
  * [5] Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra.  A strong and easily computable separation bound for arithmetic expressions involving radicals.  Algorithmica, 27(1):87–99, 2000.
  * [6] John Canny.  Some algebraic and geometric computations in pspace.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460–467, 1988.
  * [7] John William Scott Cassels.  An introduction to the geometry of numbers.  Springer Science & Business Media, 2012.
  * [8] Qi Cheng, Xianmeng Meng, Celi Sun, and Jiazhe Chen.  Bounding the sum of square roots via lattice reduction.  Mathematics of computation, 79(270):1109–1122, 2010.
  * [9] Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O’Rourke.  The open problems project.  http://topp.openproblem.net/.
  * [10] Kousha Etessami and Mihalis Yannakakis.  Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations.  Journal of the ACM (JACM), 56(1):1–66, 2009.
  * [11] J-H Evertse and Roberto G Ferretti.  A further improvement of the quantitative subspace theorem.  Annals of Mathematics, pages 513–590, 2013.
  * [12] András Frank and Éva Tardos.  An application of simultaneous diophantine approximation in combinatorial optimization.  Combinatorica, 7:49–65, 1987.
  * [13] Michael R Garey, Ronald L Graham, and David S Johnson.  Some np-complete geometric problems.  In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 10–22, 1976.
  * [14] Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, and Xin Yang.  Number balancing is as hard as minkowski’s theorem and shortest vector.  In International Conference on Integer Programming and Combinatorial Optimization, pages 254–266. Springer, 2017.
  * [15] Narendra Karmarkar and Richard M Karp.  The differencing method of set partitioning.  Computer Science Division (EECS), University of California Berkeley, 1982\.
  * [16] Serge Lang.  Algebra, volume 211.  Springer Science & Business Media, 2012.
  * [17] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász.  Factoring polynomials with rational coefficients.  Mathematische annalen, 261(ARTICLE):515–534, 1982.
  * [18] Chen Li, Sylvain Pion, and Chee-Keng Yap.  Recent progress in exact geometric computation.  The Journal of Logic and Algebraic Programming, 64(1):85–111, 2005\.
  * [19] Joseph O’Rourke.  Advanced problem 6369.  American Mathematical Monthly, 88(10):769, 1981.
  * [20] Jianbo Qian and Cao An Wang.  How much precision is needed to compare two sums of square roots of integers?  Information Processing Letters, 100(5):194–198, 2006.
  * [21] James Renegar.  A faster pspace algorithm for deciding the existential theory of the reals.  Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
  * [22] Wolfgang M Schmidt.  Norm form equations.  Annals of Mathematics, 96(3):526–551, 1972.
  * [23] Wolfgang M Schmidt.  Diophantine approximation.  Springer Science & Business Media, 1996.
  * [24] Claus-Peter Schnorr.  A hierarchy of polynomial time lattice basis reduction algorithms.  Theoretical computer science, 53(2-3):201–224, 1987.